Eu tive um problema semelhante quando um usuário foi movido para um cluster diferente do Exchange, mas o Outlook armazenou a referência anterior em cache e continuou tentando enviar para o cluster anterior, mesmo quando eu selecionei especificamente o usuário da lista de endereços global .
A maneira como consertei isso foi no Outlook, comece a digitar o nome do usuário até que ele sugira automaticamente o nome de usuário, use a tecla de seta para selecionar o nome na lista de sugestão automática e clique em Excluir. Tente digitar o nome novamente e ele não deve detectá-lo automaticamente, para que você possa selecionar o usuário da GAL.