Autodiscover versucht (neben diversen lokalen Lookups) folgende Methoden, um die Konfiguration der Konten automatisch herauszufinden:

Test via https://ihredomain.tld:443/Autodiscover/Autodiscover.xml
Test via https://autodiscover.ihredomain.tld:443/Autodiscover/Autodiscover.xml
Test über die "Autodiscover-Redirection-Method". Das ist prinzipiell ein Aufruf von http://autodiscover.ihredomain.tld:80/Autodiscover/Autodiscover.xml wo ein Redirect auf das richtige OWA, also z.B. https://owa.liveapp.ch/Autodiscover/Autodiscover.xml erwartet wird
Test via DNS SRV Record Redirection-Method. Hier wird im DNS nach einem Eintrag _autodiscover._tcp.ihredomain.tld gesucht der auf die Adresse des OWA auflösen muss
Methode 1 und 2 schlagen bei Hosted Exchange immer Fehl, da hier entweder gar keine Antwort auf Port 443/HTTPS geliefert wird oder aber (wenn z.B. ein DNS-Eintrag *.ihredomain.tld existiert) ein Webserver die Anfrage entgegen nimmt auf dem a) kein zum Namen passendes SSL-Zertifikat zurück kommt und b) unter der Adresse /Autodiscover/Audodiscover.xml auch keine korrekte Konfiguration zurückgeliefert wird.
Methode 3 funktioniert dann allerdings. Das können Sie selbst testen indem Sie in Ihrem Browser http://autodiscover.ihredomain.tld:80/Autodiscover/Autodiscover.xml öffnen. Es müsste ein Fenster erscheinen wo Sie sich mit einem Ihrer Hosted-Exchange-Accounts authentifizieren müssen. Danach werden Sie automatisch auf https://owa.liveapp.ch/Autodiscover/Autodiscover.xml weitergeleitet

Grosses Problem an Autodiscover ist, dass sich viele Mail-Clients unterschiedlich verhalten (sowohl in der Reihenfolge der Methoden als auch im Verhalten, wenn eine der Methoden fehl schlägt). Auf Mac scheint es z.B. so zu sein, dass wenn beim Aufruf von der URL in Methode 1 oder 2 ein Webserver mit SSL-Zertifikat antwortet OS X das entsprechende Zertifikat anzeigt und strikt versucht auf dieses System zu verbinden. Korrekterweise müsste OS X allerdings die anderen Autodiscover-Methoden durchprobieren, so auch Methode 3 die funktionieren sollte.

Grundsätzlich hält sich unser Exchange-System aber an die Richtlinien, wie Autodiscover gemäss Implementation von Microsoft funktioniert. Das lässt sich auch via https://testconnectivity.microsoft.com/ mit einem der Autodiscover-Tests überprüfen.

Um das Problem zu lösen erstellen Sie zusätzlich (oder anstelle) des bestehenden Autodiscover-CNAME-DNS-Eintrags auch noch den Eintrag für die SRV Record Methode (4). Dieser muss folgendermassen aussehen:

_autodiscover._tcp.ihredomain.tld. 3600 IN SRV 0 100 443 owa.liveapp.ch.
In Outlook lassen sich die einzelnen Autodiscover Methoden konfigurieren. Details dazu finden Sie hier: http://www.careexchange.in/outlook-autodiscover-methods-with-exchange-2013/