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