Exchange Online - Outlook 2013 Profilneueinrichtung sehr langsam

Hallo zusammen,

zuerst zur Infrastruktur: Ich habe ein lokales AD welches per Dirsync zu MS rüberkopiert wird. Die Authentifizierung von aussen erfolgt mittels ADFS.
Ich habe zwar noch einen lokalen Exchange am laufen aber dieser macht nur noch ein wenig SMTP Relay Arbeit für ein paar Drucker. Dementsprechend kann ich den Exchange auch schmerzfrei ausschalten - alles läuft weiter.

Wenn ich am Client ein nslookup autodiscover.meinedomain.de eingebe kriege ich folgendes zurück:

Server: dc01.meinedomain.de
Address: 192.168.0.2

Name: autod.ms-acdc.office.com
Addresses: 2603:1026:203::8
2603:1026:203:9f::8
2603:1026:208:88::8
2603:1026:203:65::8
40.101.61.120
40.101.124.24
52.97.139.184
40.101.124.216
Aliases: autodiscover.meinedomain.de
autodiscover.outlook.com
autod.ha.office365.com

Sieht für mich auch okay aus.

Jetzt aber das "Merkwürdige". Immer dann, wenn sich ein User neu an einem beliebigem Client anmeldet, dauert das "Finden" des E-Mail Accounts relativ lang. Wir reden da von ca. 5min bis der User gefunden wird und sein Kennwort erneut eingeben muss. Danach läuft alles ganz normal weiter und es gibt im weiteren Verlauf auch keinerlei Probleme mehr.

Ein erneuter Outlook Start geht auch ohne Probleme. Die Firewall blockt da auch keine IP Adressen in dem Moment.

Jemand eine Idee ?