Por muito tempo tive uma dor de cabeça cada vez que formatava um pc com Microsoft Outlook 2003, pois os clientes por mais orientados que sejam, não criam e adicionam os seus contatos num arquivo de contato.
É mais fácil sair digitando os endereços e deixar o Outlook guardar…, bom, depois de alguma pesquisa na internet achei o dito caminho.
Os endereços autocompletáveis ficam gravados no arquivo Outlook.nk2.
WindowsXP
C:\Documents and Settings\nomedousuario\Dados de aplicativos\Microsoft\Outlook
WindowsVista
C:\Users\nomedousuario\AppData\Roaming\Microsoft\Outlook
Pronto, agora é só copiar esse arquivo na hora do backup e seu problema esta resolvido.