Supongo que el Outlook te los eliminó porque al no estar los contactos en tu PDA (y ser ésta la que tiene el cambio más reciente) los eliminó del propio Outlook. Creo que si recuperas de la papelera los contactos, cuando vuelvas a sincronizar la PDA los tendrás todos otra vez. Aunque te recomiendo que desconectes la PDA del PC, recuperes los contactos y hagas un backup del Outlook, por si acaso. Entonces conecta la PDA para sincronizar.
Y para el futuro, convendría que periódicamente hicieras un backup de la agenda, el calendario y los mensajes con herramientas como PIMBackup. Por si las moscas...