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?