La verdad que nunda me ha pasado, aunque sí me ha pasado tener contactos de hace siglos y desaparecer misteriosamente, alguno de ellos. Creo que gmail, desde la web, tiene una opcion para reponer contactos borrados. También sería bueno que cada 1 o 2 meses te bajaras el archivo de contactos a tu ordenador o memoria externa por los "porsiacasos".
Como poder pasar puede que sea cualquier cosa. Desde eso que haya sincronizado mal y haya borrado contactos, alguna aplicación maliciosa, o no lo sé.