I have (in the last 4-6 weeks) been seeing a similar problem -- apparently an excellent connection, but very few search results returned, even for search terms that should have had many results. (I have not had the problem of unrelated results.)

I tried running two limewire processes (as two different users) simultaneously, and found that one was returning few or no results while the other had many results for the same search terms. Interestingly, when looking at the "Connections" panel, most of the ultrapeers that the first one was connected to had high "Dropped I/O" rates (50-60%), while those that the second one was connected to had much lower Dropped I/O rates (20%-30%). I don't know whether this is the reason for the few search results the first one returned, or just a coincidence.

Anyway, now what I do is to go and manually remove ultrapeers that have high Dropped I/O rates. When I do this, the quality of my searches seems to go up as well. Again, I don't know whether this is a causal effect or just a coincidence.

FWIW, I'm running a modified version of Limewire v 4.14 (modified to connect to 8 ultrapeers) on Fedora Core 9 Linux.