What if the hashed phone number is stored as an event signed with a unqiue private key? That private key is stored on the user's behaf by the app which published the event. The app or service that finds matching phone number hashes then publishes a connect request event to the phone numbers public key, signed using the requesting user's private key. The phone number user can then see the connection request, and choose to accept or deny.

I've been thinking about building the general use case for this in AKA Profiles, where badges are always published using a unique private key, allowing badges to be discoverable, but not directly attributable to a user's public key without their permission.