What's the output of https://www.testexchangeconnectivity.com/ and the "Outlook Autodiscover" or "Exchange ActiveSync Autodiscover" tests? I've got a sneaking suspicion that you've got a certificate name mismatch somewhere; if so, this test will put some big 'ol bells-n-arrows on it.
This is a Microsoft-operated site; you should use it with a test account (it'll tell you so). When the test is complete, click the "Expand All" dropdown at the top of the screen and look for any red "X" in a circle -- the ones down near the bottom probably describe your issue.