I like your focus on improving UI but I think you need to do some customer development work. Figure out whom to target and fulfill their search needs.
E.g.: We need search for hardcore search users. 100 results above the fold. Clear ways to influence the algorithm. Shortcuts to search for specific meta-data. Etc, etc.