It's not a perfect solution, but I don't understand why Path don't hash the contact details before uploading them, and check against the hashes. You can still infer all kinds of social graph information, of course, but they're at least not consuming raw contact details.
You cant guarantee a unique hash. When you hash users' data there is the possibility of collision; this probability grows with every new user. Without identifying data of some sort, it's difficult (impossible?) to get the exact user.