Google-style search is essentially a solved problem. I wouldn't be surprised if Google's rankings are already close to "optimal" for the top 10 results.
This would mean that it would be impossible to ever beat Google because small ranking improvements would be insufficient to convince users to switch in large numbers.
The only way to improve search is using verticals as Bing is doing.
But you need to take this much further, opening up a vertical search API so that developers can extend the search engine in thousands of verticals competing with each other whereever there is overlap.
Directed Edge is already looking at the world that way. I'm not claiming they're the startup that will make Google irrelevant. Historical precedents suggest it's still early for that. But it seems extremely unlikely that nothing ever will.