In spite of a couple of dozen alternatives, Google has web-search pretty much locked up at the moment. What I think the world needs is a developer component you could drop into your application and use as the full-text search piece of your software that works as well as Google.
The problem is that any time I use the embedded search feature on a forum, wiki, blog, etc. It reminds me of doing a web search in 1997. It takes a lot of time to narrow down your search terms enough and/or click through pages of results to find what you are looking for. It seems very primitive. Yes, some web-facing apps can be indexed by Google so that is a workaround but many of these sit behind a firewall on intranets.
The Google mini is another solution but it's not something you can ship with your products. So your customers end up having to connect to it and maintain it and this adds to the overall cost of your product. Also, are the relevancy algorithms in the Google mini the same as web search? I would think there should be different heuristics for each app that should be tweakable by the developer.
There is Lucene, but I've been disappointed by the search results in applications that use Lucene for search, so I am assuming that there hasn't been a lot of progress for relevancy algorithms outside of term frequency. Although, it does indexing and searching really well.
This could be an area to focus on for one of the startups who are trying to challenge Google in the web-search market.