Properly implemented rate limiting would be a better way to achieve that though. That is were the 'blinding signature' part comes in: to give the server the possibility to intelligently rate limit.

Rate limiting is a terrible solution to this sort of problem IMO. It just forces the attacker to be patient, but they will eventually get what they want, which is name/phone number pairs of the entire numeric space of phone numbers. His solution is problematic because it distributes the burdain to the user, and anyone who's gotten massive numbers of friend requests on a chat service can attest to how unfriendly that is, but it's on the right track. It should not be possible for an attacker to get contact information for arbitrary phone numbers through an api. Something should gate that, probably through the mutuality of having each other on each other's contact list.

We're not necessarily talking about sharing contact information; all we're talking about here is an acknowledgement of existence.

Given that context, due to the nature of the problem, rate limiting is by definition the -only- solution to the problem (if I'm understanding the problem correctly.)

You do have a point that perhaps the question we should be asking should be 'how do we detect mutual connections,' but that's another story altogether.

Under what circumstances do I want someone who I have not even enough interest in to put in my phone's dialer to be able to ping my phone number and get my name back?

The question of whether services should even be DOING this kind of open book "does this phone number have a user attached and what is their name?" query is more fundamental than any other question, imo. It's not another story, it's a skipped first story.