The negative results problem with search engines
Here is another problem that I see for new search engines, ones that people are unfamiliar with (to go with yesterday's other set of them).
Not everything is on the web, or at least not everything is findable in search engines with a sensible amount of effort. This means that when you get what is essentially a negative result in a search engine, you're confronted with a question. Did you phrase your query badly (for this search engine), or is there really no sensibly findable result for what you're looking for?
The more familiar you are with a search engine and how to write queries for it, the more you can feel confidant about which option is the correct answer. The less familiar you are with a given search engine, the more uncertainty you have. If you care about the results, this uncertainty means that with an unfamiliar search engine you're going to wind up spending more time convincing yourself that no, really, there really are no results for this (as you try different searches, different phrasing, and so on).
(This is the related issue with negative results that I was referring to in yesterday's entry.)
Sidebar: what a negative result is
The obvious negative result is 'no pages that match your search', but this rarely happens for most non-artificial searches these days. Instead, a negative result can be summarized as 'no useful links appear before your eyes glaze over trying to find them'. In practice, a useful link on page ten of your search results might as well not exist; you're extremely unlikely to see it.