I think the problem with search is that while it's relatively doable to build something that is competitive in one or a few niches, Google's real sticking power is how broad their offering is.

Google search has seamless integration with maps, with commercial directories, with translation, with their browser, with youtube, etc.

Even though there's more than a few queries they leave something to desire, the breadth of queries they can answer is very difficult to approach.