Lot's have tried and failed to topple the mighty Google, but this one caught my eye as having half a chance. Why? Well, they've already indexed 120 billion pages and are showing some decent results in searches.
Also, their board consists not only of ex-Google employees (including Anna Patterson) but also the founder of Alta-Vista, Louis Monier.
I'd keep an eye on this one - could get quite big...
http://www.cuil.com