> terrible search interfaces

I'm not too unhappy with Google Scholar lately. It seems to have nearly complete coverage of anything that can be found in an online paper archive (both institutional archives and journals' own archives), and a better search interface than those archives do. Via extracting references it even indexes a large amount of older material that's not yet digitized; of course it can't link you PDFs in that case, but it still provides the citation and can return offline papers by title/author/date in search results.