Problema: os usuários estão tentando enviar para um valor LegacyExchangeDN (endereço X500).
Correção / solução alternativa: excluir endereços de preenchimento automático no Outlook deve resolver isso.
Problema: o endereço X500 listado contém caracteres que não foram traduzidos corretamente de alguma forma. + é um indicador de algum tipo de tradução que ocorre. +20
é igual a space
. (Isso pode ser um sintoma falso, continue lendo ...)
Correção: pode ser de várias fontes diferentes. Observe os objetos do usuário e veja se eles têm endereços X500 atribuídos. Nesse caso, eu preferiria procurar no Active Directory, mas as informações também devem ser expostas no Centro de administração do Exchange.
Você diz que adicionou um novo domínio ao servidor do Exchange e foi aí que os problemas de "coabitação" começaram. Eu recomendo que você faça referência a este artigo technet sobre como adicionar um segundo domínio autoritativo no Exchange: Configure Exchange para aceitar emails para vários domínios autoritativos . É possível que exista uma configuração faltando.