A server receives an instruction to verify that a contact point (e.g., a phone number) is associated with a name. A set of users that have the contact point stored in a contact list on the server is identified and client devices associated with the users in the set are sent a name verification query. The name verification query includes a representation of the name and the contact point. The server receives a set of one or more matching scores from each of at least a subset of the client devices. The set of matching scores received from a given client device indicates a degree to which a name stored in association with the contact point in the client device's local address book matches the representation of the name. A determination is made as to whether the contact point is associated with the name based on the received matching scores.