Over time, hardware gets cheaper, and the cost of building a search engine declines. This has not been matched with a reduction in ad density. The cost improvement is going into Google's profit margin. That indicates a vulnerability.
Google has some striking weaknesses. The two I focus on are provenance and business background. I've done work on business background (see "sitetruth.com"). That tries to find the real-world business behind a web site that's selling something, and then uses the data available about real-world businesses to check it out. That can then be fed into search result ordering. SiteTruth is a demo; it's running off free data sources. Paying for higher quality data from Dun and Bradstreet and other non-cheap sources would make the business background check much better.
Google's other big weakness is provenance. Search engines should find the original source of information. Much of the Internet is sites scraping other sites, linking to other sites, and commenting on other sites. We see this on HN all the time, where someone links to an article, but the actual source is two blogs deep. The original source should be the primary search result, perhaps annotated with notes about the more heavily promoted sites mentioning it. This means more attention to when something appeared and better matching of content. Google already does this for news. For ranking purposes, attention metrics for scraper sites need to be credited to the original source, not the scraper site.
One possible customer for such a system is Bloomberg. The people who get those expensive terminals could use both of those features. Then offer it to the better universities, so that students grow up using something less consumer-oriented with Google. That strategy worked for Facebook.