Maybe it's difficult to topple the giants, but you should not pick Cuil as an example. Cuil was awful and it died because it put unrelated information together. It certainly did not "still [do] the job perfectly".
If you want a better example of a good search engine with decent results that has failed to compete with Google it would be Bing. If you use this blind search tool: http://blindsearch.fejus.com/ that returns results from both Google and Bing. Bing is winning in terms of most relevant results and yet has failed to really steal away any of Google's user base in the long run is this not more than enough proof that people don't care if another search engine returns better results? I think it does.
There are people out there who think Google is the Internet, hows that for brand recognition? People who don't even own computers or don't have the Internet have most likely heard of Google at some stage in their lives.