So this solution would waste a bunch of storage space.

Doesn't exact search on DHT usually work with bounces? Nodes relay the search (to less and less nodes depending on the number of already made bounces), and if a node with a positive result isn't connected to the node that originally sent the search, then connect to it. I saw a few DHTs using this technique succesfully. Clearly doing the same for fuzzy searching isn't possible as there is not positive (1) or negative (0) results, but also anything in the middle.

Seriously man, I'm very interested if your solution could work, and I'd rather see schematics or code rather than text. It would be much clearer to me.