I'm not so sure about that. nostr.directory create “verified” link with keys by centralised entity. I don't think we can do that without centralised entity and I don't think we want real email address linked publicly with keys. I think this is more for “find you old acquintances and friends,…”. when user can do verification of identity himself, but he just don't know about other side using nostr.

What i have on mind is just storing salted hashes (salt month and year maybe also relay url - i don't want universal cheap rainbow table, notes can expire after month nip40) on relay with new keys, so hash is not linked with main identity on nostr.

Searching one can ask relay for hashes (i think we need relay which is able filter notes by content, im not sure if we have one.). When he find someone he can use DM for verification of identity and exchange main pubkey…