Interesting idea. But the address book "friends" must be mutual for this to work. You would miss those contacts that don't have you in the their contacts.
It seems to me like that fits somewhere in the space between "small compromise" and "bonus feature". This idea seems like a very good practical solution--I'm very curious what moxie's take on it would be.
If the design goal is to not trust the server, it is still pretty useless.
Say you make the hash take 1 second on a phone. Without trying to really pin it down, I think an attacker would be able to do an area code in hours with minimal investment. They could do the entire phone number space fairly quickly for a modest investment.
(My attacker there is focusing on the pairs for one number. The area code part comes in because phone numbers really are lumpy like that.)
If they don't have you in their contacts it's probably for a reason. A lot of times (not all, but more than enough) it's probably because they've basically stalked you.
