Probablemente los contactos los tengas en el Ms Outlook y no en el Ms Outlook Express.
1. Fijate si tenes los contactos, si aun existen.
2. Revisa en el ActiveSync si has creado correctamente la sincronización y si has tildado la casilla de chequear contactos.
3. ¿Has hecho un cambio de ROM o algo por el estilo cuando borraste los contactos? No debería pasar nada con ello, pero a veces quedan mal instaladas.
Miralo bien que debe de ser alguna cosa por el lado que te indico.