There is one trick you could use, query by "title artist", because pretty much everyone names their files "artist - title" the bad responses should end up with the two reversed (i.e. in query order). This only works until they use the same query, or rewrite the response, and pretend to have an identical copy of a file that someone else has. But then they pick up the bad response generators as well, which will still identify them as fakes.

The thing is that gnutella is conceptually very weak when there are rogue sites. A site can claim to see many peers and accept anyone who connects, but never forward queries or only return faked or rewritten responses. You could even use that to DOS some random other site, i.e. claim that a specific IP has everything ever requested. It just isn't a very solid protocol, and it has several well researched scalability problems.

edit: In the end, the best thing is probably to just generate a nice listing of artist/song suggestions and leave it at that. Someone can print the list out and visit the friendly local record store, or ask friends whether they have or heard of the artist/song, or look for a sample of the music through the various sources on the internet