Key strengthening can help. If you do a bcrypt-style hash and set the cost so as to take one second on a modern CPU, brute-forcing each phone number would take about 57,000 days :)

I would be more comfortable with this than giving them my entire address book, anyway.