OK i know this thread is pretty old but the problem has only gotten worse. I started thinking of some fundamental changes to the software that could (potential) be a fix.

I use frostwire which I understand is open source. I plan on taking a look at the code this week to see how feasible this might be. Basically we need to verify our hosts before we display them in the search results. Here's what a conversation might look like now.

mycomp: Hey do you have this file "filename.ext"?
spammer: yeah i have "filename.ext"
mycomp: ok thanks, ill display it in the search results

What we need to do is verify the host is not automatically generating files before we consider them having the first file. Like this:

mycomp: Hey do you have this file "filename.ext"?
spammer: yeah i have "filename.ext"
mycomp: ok, well do you have "sdfgisdf.ext"?
spammer: yeah i have "sdfgisdf.ext"
mycomp: you must be a spammer because "sdfgisdf.ext" likley does not exist, ignoring search result.

What do you guys think? Without knowing a lot about how gnutella works i think this could be possible.