What if the phone number just gets associated with an independent keypair, and instead of a "search" occurring, a sort of encrypted inbox is utilized?

Someone adds their phone number to nostr by having this new and unique keypair that is indexed by the phone number.  When a user tries to find their friend, they receive the associated keypair.  This user then deposits an encrypted payload identifying themselves, perhaps even including a phone number if it exists.  This would allow many different UI flows, including contact matching.

The original user who added their number in this way can check on the status of their "encrypted inbox" by requesting new events to the inbox.  Only the user controlling the private key would be capable of decrypting the inbox, so it likely wouldn't need to even verify they own the inbox.

Once the user sees that their friend is there (a suggested connection, or some way to vet users requesting access?), they just add them and a connection is made.

There would be some things to work out, like proving you own the number, and protecting anonymity of the person registering this encrypted inbox (built in, multi-hop, encrypted relaying?), but seems like this sort of flow could function.