Not that small. It's comparable to a weak password. There are about 5 billion active phone numbers in the world [1].

Besides, a small search space can only be searched quickly if it takes little time to a hash a phone number. Doing a few billion MD5-sums is not so difficult. If the hashes are computed with an expensive bcrypt then it's just a matter of increasing the number of iterations to make brute force attacks unfeasible.

Edit: I realize that the hashes can't be salted (because different phones must produce the same hashes for the same phone numbers), so a rainbow table can be created for the entire database.

[1] http://www.cbsnews.com/stories/2010/02/15/business/main62097...