Its seems that search (at least text search) is more or less a solved problem. Trying to innovate in the search space today is more or less as futile as trying to innovate in the operating systems space about 10-12 years ago. Noone really cares given that the state of the art works quite well.
Just because operating systems all look the same from far enough nowadays doesn't mean no innovation is possible. As an example, we are slowly moving from the old file/directory organization of files to a less hierarchical system (tagging). Or maybe we could destroy the notion of files completely?
No, the search problem is not solved. When I look at the referrer logs of my site, I find people coming from as high as the 100th search result page of Google. My experience with searching on the Internet also leads me to believe that search needs to get better and better. A lot of very interesting things are happening in the search field; vertical, social, etc..
But, I will have to agreed that the major Search Engines are extremely good at the present moment. I use Yahoos Search API on my site, and am happy to fiddle around with their API's rather than build my own crawler (although I have real people adding links).
