IMHO, though, i think the normal search engine becomes more like a marketing game now. Same as "most people prefer something other than Coca-Cola in blind test", yet they are still the biggest seller by far.
Unless something is changing in the landscape that affect users behavior (like social web - led by FB, Twitter etc), i wouldn't expect anyone can win against Google in this game without MUCH higher value propositions.
Search is funny that way, you know instantly if a search engine is 'good' or 'fluff'. Most engines out there today are very comparable wrt to the quality of the results, some are better in one domain, others are less susceptible to spammers but overall there is not that much difference, it's comparable to different tastes in icecream. EDIT: once you've got a user they're not likely to switch away from their favourite flavour, it's what they're used to.
But if some group came along that quietly and without fuss presented you with a search engine that had exactly what you were looking at on page one every time I think the current crop would fade faster than you could say 'altavista'.
Google's strength is obviously in brand penetration when it comes to search engine. After all, most people outside us hardly even know about "Google Chrome" after making such a huge splash all over the place. (http://www.youtube.com/watch?v=o4MwTvtyrUQ).
So, i wouldn't expect them to type in www.cuil.com or WolframAlpha without something is changing in the landscape that alter user behavior.