Slow hash function + salt would solve this.. e.g. you'd be lucky to do more than 10 hashes a minute with bcrypt and 20 salt rounds.
It's just not hard enough to guess a potentially valid phone number. With passwords, hashing only helps because the probability of a valid password is _very_ low, and because you don't need to look up a password, only check if it's the right one for joeblow (so you can salt them individually).