I have this issue. the customer had mail.domain.tld and with a new certificate it must be webmail.domain.tld
I ran all the scripts to change the internalurl and the external url
all internal outlook clients give the popup that the name in the certificate doesn't comply with the server. outlook says it connects to mail.domain.tld but the cert of course is for webmail.domain.tld
I recreated outlook profiles to connect to webmail.domain.tld by hand, still the same popup.
recreating a profile and let all the settings come automatically goes without a problem, and on the proxy tab it says outlook has to connect to https://webmail.domain.tld
still this error keeps coming back.
I have installed numerous certs on exchange servers with public domain names and changed the settings to use that public domain name and that goes fine from internal and external.
btw.. configuring outlook client somewhere on a pc on the internet to connect to a mailbox on that server functions as it should be. it connects with webmail.domain.tld