I've also been thinking about this. Relays should be in a p2p DHT and index and retrieve hashes of notes and pubkeys for each other.