¿Y no puedes volver a sincronizar con Gmail para tener otra vez todos los contactos allí y luego exportarlos a Outlook? Aunque claro, si lo último que hiciste fue borrar contactos desde la web, igual al sincronizar se te borran los del móvil, no sé. Seguramente habrá algún programa, pero yo no conozco ninguno.