Acho que você encontrará o preenchimento automático que aparece quando digitar nomes no campo Para não está fazendo uma pesquisa de catálogo de endereços - ele está varrendo um cache local que lista freqüentemente / usado anteriormente contatos (de listas globais e locais).
Veja um artigo de suporte do MS que explica como redefinir o cache (em caso de corrupção, etc.).
Eu não sei se isso vai ajudar no seu caso, então obviamente faça backups .
Você também pode me interessar em tentar Ctrl + K depois de digitar a primeira parte de um nome - é a tecla de atalho para Verificar Nomes e irá substituir o nome parcialmente digitado por uma correspondência completa, se existir apenas uma, ou pop-up uma caixa sugerindo as várias correspondências no caso em que encontrar várias. No entanto , tenho a sensação (não confirmada) de que isso só funciona com a lista global, não local.