Você está configurando os clientes externamente ou internamente (e ambos falham)? Você pode esfregar & postar saída de:
Get-OutlookProvider
Get-OutlookAnywhere
Get-ClientAccessServer
Na maior parte do tempo, vejo problemas com esses valores.
AutodiscoverServiceInternalUri. InternalHostName & ExternalHostName.
Requerendo SSL? Método de autenticação? Suponha que você tenha um certificado gerado pela CA instalado e confiável por clientes (algumas CAs também exigem o certificado intermediário instalado).