Just spotted a NYT article on a new search engine called cuil from Anna Patterson and Tom Costello. A while back I read Dr. Patterson's article "Why Writing a Search Engine is Hard". Nice quick read on the issues. I also stumbled upon several patents she wrote.
So the recent challengers of note are Ask.com, Powerset, Hakia, Wikia, Mahalo and now Cuil. I'm rooting for the algorithmic ones, not really sure how Wikia and Mahalo can scale to be non-niche engines.
While I hope Cuil is successful (I like to see Academics go out and build companies), I'm not sure that it's possible to beat Google at this point. It seems far more likely that Microsoft will just try and swallow Hakia and Cuil and attempt to brew something out of the parts.
I recommend reading Danny Sullivan's post on Cuil, he hit most of the obvious points.
I still think building intelligence on top of an existing index/engine is the way to go and I'm not sure that bragging about your index size or your back end architecture is going to get you any meaningful marketshare.
Also, Enterprise Search is still far behind in NLP technology vis-a-vis the big 4 and the NLP startups. It's still 1999 there, enterprises are just now figuring out how to expose their vast document sets to an internal crawler and provide a UI that is not overly simplistic for savy users. They've tried the classic approaches of commodity engines and found them wanting. Link analysis doesn't help either as most of the these documents are not web documents with links. This just cries out for an approach like Vivisimo's clustering + Hakia's semantics + Delicious' user driven tagging.
Corporate searchers need a good advanced interface and results that can be grouped by things like time and originating department.... but not be forced to drown in overly similar hits. That is a market worth getting into with a $33M VC investment. The landscape is littered with vendors that over-promised during the sales cycle and Enterprise customers will switch products if it solves the problem better.
Look at the $500M acquisition of Verity by Autonomy in 2005. That's 5X more than Powerset (in 2005 dollars) and they actually had loads of paying customers.
I worry that going directly at Google with a consumer search engine is just so much tilting at windmills. Sometimes just selling a product to people willing to pay for it is easier.