Cuil seems like a case study in launching too soon. There was nothing wrong with their offering, as such, but they launched before it was ready and paid the price. Shame.
except it didn't work ~ http://www.flickr.com/photos/bootload/2710119638/ a quick search for common words I knew of revealed little ~ http://www.flickr.com/photos/bootload/tags/cuil/ and the HN verdict at the time ~ http://news.ycombinator.com/item?id=258737
you're right, as an earlier post suggests it was half-baked & released much too early. How much of the web surface has google indexed compared to what is there?
The the machines with the best results for your keyword went down the front end just displayed what it had - which often was unrelated stuff from all the other machines that did reply.
Or in other words the lack of relevancy was due to the overload, not in principle due to their search algorithms.
Nowhere was this more apparent than with "Cpedia" - a project they made available to the public at some point after the main launch. What it was supposed to be was an online encyclopedia (like Wikipedia) based on data automatically collected from their web crawler. What it ended up being was a gigantic pile of Markov spew; ridiculous, rambling, often incorrect, and useful to no one.