Vuoi dirmi che reinstallando il sistema operativo hai perso solo la rubrica? Io credo invece che hai perso tutto e quindi: 1. hai ricreato l'account 2. usando imap, hai ancora la posta sul server.
Se non hai fatto un backup della cartella del profilo prima di formattare la rubrica l'hai persa, a meno che vuoi tentare con sw specifici di ripristino di file cancellati.