After Migrating Exchange server 2013 to 2016 clients kept getting the above message. I ran the following command to the correct domain name:
Set-ClientAccessService -Identity ServerName -AutodiscoverServiceInternalUri https://externaldomain.com/Autodiscover/Autodiscover.xml
I then had to run the Hybrid Configuration Wizard again.
References:
https://serverfault.com/questions/627870/outlook-security-alert-the-name-on-the-security-certificate-is-invalid-or-does
https://docs.microsoft.com/en-us/powershell/module/exchange/client-access-servers/get-clientaccessservice?view=exchange-ps