Large music databases, iTunes, CDBaby, Amazon, etc, use a cacheing device to improve the efficiency of their searches. This device makes the most popular search results more readily available than the rest, which works well for most searches (on a zipf curve distribution). However, it significantly disadvantages the less-popular artists/results - to the point of virtual exclusion - for example, on searches for versions of "The Lord's Prayer" in iTunes, in which the versions by the more popular artists drown the versions by less popular artists ...
That's likely a bug in their particular software implementation, not a bug in the intellectual idea of database caches. What *should* happen, should your search not result in any hits in the cache, is that the site's software issues a hugely more expensive search against the whole dataset. If you're seeing a truncation due to a particular search term being less than popular, it seems likely that the site operators would appreciate the generation of a reproducible bug report. Several sites (livejournal, citeulike, etc) use memcached for this sort of database caching - and it doesn't seem to have the 'ill' mis-behavior that you're describing. --e