It seems to me that a way to potentially creep up on google would be to make a specialist search engine. Some topic area that google is not so useful for searching on. Make a search system that 'understands' the domain in question, allowing it to index and search it really effectively. As a random example, say, a movies search engine. If it could be consistently more useful than google for finding out information abo…
It's like what we're doing over at bug.gd-- building up an error-based search engine. Our upcoming version (we hope to announce in the next month or so) will have a variety of techniques optimized for searching for errors on the web. (E.g. filtering of user-specific "noise" in error messages, better integration into software, etc.) With the added bonus of capturing feedback from users that can be used for future users and for software writers.
We've been seeing some great uptake lately, so I'm bullish on the vertical search space.
We've been debating on a two-column search results page for our redesign, so we're watching cuil's success closely to see how people like that kind of presentation.