Y es muy fácil que los contactos los tenga respaldados en google...
Puedes entrar en gmail.google.com con sus claves, y ver si están los contactos. Yo suelo decir que no me los copie, pero todos conocemos a google, y en alguna actualización, se desactivan "por error" ciertas configuraciones, y por más cuidadoso que seas, acaban copiados en sus servidores.
Un saludo.