Si los contactos de la pda son "más viejos" que los del outlook en el pc, y en el outlook NO tienes contactos, es normal que se te borren. Digamos que el active sync "entiende" que lo último que has hecho es eliminar los contactos. Prueba a editar o añadir algún contacto a la PDA (sin tocar el outlook) a ver qué ocurre: en teoría debería añadirlo/editarlo en el outlook.