How hard would it be to ask for search feedback on search results, perhaps piloting with some small subset of zero-result searches? For 1/1000 ZRRs, prompt the user to provide some type of useful information about why there should be results, or if there ought to be, or what category of information the searcher was looking for, etc. You'd get junk and noise, but it might be one way to filter out a lot of the gibberish. You could also ask people to agree to make their failed search part of a publicly visible list, although this could of course be gamed.