We had to meet a similar requirement and used hardware anchoring. Instead of a hash, think of a keyed HMAC style operation where the HMAC secret is inside an H

We had to meet a similar requirement and used hardware anchoring. Instead of a hash, think of a keyed HMAC style operation where the HMAC secret is inside an HSM. HSM operations are handled by a separate team than webapp. Key is not extractable. It is not vulnerable to brute-force in the same way as a hash because the function cannot be executed outside your computing environment. Of course an attacker can still try to brute-force, but only using the app or from inside your environment. So you have to apply appropriate rate limiting controls and monitoring on your "boat anchor" HSM for it all to work out. For this application I would probably look for "proof of ownership" of the number or email before allowing a query.