There are two ways you can set up Exchange's Autodiscover service, assuming a SMTP domain called "example.com":
In both cases, the name should resolve to your Exchange server(s) both from your internal network and from the outside (usually via a reverse proxy and/or firewall); if you have more than one Exchange server, a load balancer should be placed in front of them and configuration should be modified accordingly; also, the certificate used for Exchange web services (be it on the server(s) or on the load balancer / reverse proxy) should contain as a SAN the name you are using for the service.
It seems like your external publishing of the service is ok, otherwise the Remote Connectivity Analyzer would fail; but what about your internal network?
Are you using the same name ("example.com") for both your SMTP domain and your Active Directory domain? If this is the case, the FQDN of the domain will automatically point to your domain controllers in the internal DNS, thus it can't point to your Exchange server(s).
If instead "example.com" is a different domain from your AD one, are you using split-DNS (i.e. do you have an internal DNS zone with the same name)? And in this case, did you make the FQDN of the domain point to your Exchange server(s) from inside your network, too?
TL;DR: make sure "example.com" points to your Exchange server(s) both when resolved in the internal network and when resolved outside it; if this is not feasible, switch to a specific name ("autodiscover.example.com") instead of using the FQDN of the domain; and in that case, make sure the certificate used by Exchange web services contains the appropriate SAN.