Os dados de preenchimento automático de endereços de e-mail são salvos em um arquivo 'N2K', localizado em:
C:\Users\%username%\AppData\Roaming\Microsoft\Outlook
Lá, descobri que o Outlook criou um novo arquivo '% username% .N2K' e renomeou o anterior para '% username% .N2K.old'.
Tudo o que eu precisava fazer era excluir o novo arquivo, remover o '.old' do nome do arquivo antigo e reiniciar o Outlook 2007. Isso restaurava os dados de preenchimento automático.