Você está realmente procurando em sua pasta de contatos ou clicando no botão addres bbok (ou no botão Para em um novo e-mail)?
Pode ser que seus Contatos tenham sido migrados corretamente, mas a pasta Contatos não esteja marcada para ser usada como um catálogo de endereços do Outlook. Clique com o botão direito do mouse em Contatos, escolha Propriedades > livro de endereços do Outlook > marque a caixa