Like any Exchange admin I too came accross connectivity issues from Outlook client to Exchange
The issues which I faced with both Exchange 2013 & 2016, with Outlook 2013 & 2016, it kept on asking the users for password, no matter what I did, the issue could not be resolved.
Finally the following steps resolved this issue and all users are now happy.
lets us assume we have mail domain as mymaildomain, your External hostname & Certificate name is mail.mydomain.com
open exchange management shell and run the following commands
first we set Outlook certificate name
Set-outlookprovider expr -certprincipalname: "msstd:mail.mymaildomain.com"
Set-outlookprovider exch -certprincipalname: "msstd:mail.mymaildomain.com"
then we set outlook authentication & the way outlook should treat the connection settings
Set-outlookanywhere -InternalHostname mail.mymaildomain.com -ExternalHostname mail.mymaildomain.com -identity "EXCSrv\Rpc (Default Web Site)" -InternalClientAuthenticationMethod ntlm -ExternalClientAuthenticationMethod ntlm -internalclientsrequiressl $true -Externalclientsrequiressl $true -IISAuthenticationMethods basic,ntlm,negotiate
Dont forget to change the mymaildomain name to reflect your mail domain.