I have an idea, although it would probably only work between like peers.
When you fire up the client and establish connections to other nodes, you get passed a manifest of everything those other nodes have on their systems as well. That way, when you get a search request with a TTL of 1, you can quickly compare it to those lists, and if it doesn't match anything, you can drop the request.

The lists could also be kept fresh with delta updates as well, I guess.

Are they already doing something like this? Is it even feasible?

Some clients try to cache search results, I don't know if they are picky about how close the files are to their connection, but I think it would be within about TTL 5 most of the time.
When they say Gnet can't scale, I think they forget about this because for every one host that replicates a search result of another, you reduce the "net" load to half. So try to simulate that on some super computer and let me know how your math comes out.

http://www.limewire.com/developer/GDFDoc.htm

Limewire has done a study on this and there is merit to it... but the problem lies in how often do you broadcast the files to everyone...

I think that allow the network to organize itself with clip2 reflectors may provide a nicer solution to this. Then you have 2 different cache hosts 1 for high speed and 1 for dial up. All of the people on dial up will ping a cache host of people running reflectors, all high speed users will ping a cache host of other high speed. The reflectors automatically answer queries for other servants. If you included these reflectors in all servents and then setup up the proper defaults for dial-up and high speed connections that would reduce the network traffic a lot... especially since the dial-up users very rarely are the ones actually hosting files so they wouldn't be answering unnesscary queiries.