Exchange 2010: User können teilweise nicht per SMTP (TLS) senden (Outlook, Thunderbird, AppleMail)

Moin,

wir haben seit gestern ein neues Exchange Cluster im Einsatz und einige User melden nun, dass sie keine Mails versenden können.
Dies scheint nicht Betriebssystem oder Client-spezifisch zu sein.

Erlaubt wird nur eine Verbindung via STARTTLS und IMAP/SMTP (Clients sind soweit auch korrekt konfiguriert)

Per Registry ist auch nur TLS1.0, TLS1.1, TLS1.2 (SSLv2/v3 deaktiviert) erlaubt, sowie diverse Ciphers deaktiviert:

AES 128/128 (Enabled = 0xffffffff)
AES 256/256 (Enabled = 0xffffffff)
DES 56/56 (Enabled = 0)
NULL (Enabled = 0)
RC2 128/128 (Enabled = 0)
RC2 40/128 (Enabled = 0)
RC2 56/128 (Enabled = 0)
RC4 128/128 (Enabled = 0)
RC4 40/128 (Enabled = 0)
RC4 56/128 (Enabled = 0)
RC4 64/128 (Enabled = 0)
Triple DES 168/168 (Enabled = 0xffffffff)

Außerdem Hashes:

MD5 (Enabled = 0)
SHA (Enabled = 0xffffffff)

KeyExchangeAlgorithmus:

Diffie-Hellmann (Enabled = 0xffffffff)
PKCS (Enabled = 0xffffffff)

IMAP & SMTP Ports sind in der Firewall erlaubt, die Probleme bestehen leider auch nur außerhalb des Unternehmens. Allerdings werden auch keine Verbindungen von außerhalb geblockt, die damit in Zusammenhang stehen könnte (IMAP/SMTP).
Lokale Firewall ist deaktiviert.

OWA funktioniert ohne Probleme. Port 135 für Exchange Zugriff ist nur intern erlaubt, aber da die Clients ja per IMAP/SMTP angebunden werden, wird das ja nicht das Problem sein.

Allerdings sehe ich viele Fehlermeldungen von Schannel (36888 & 36874), z.B.:
Eine TLS 1.0-Verbindungsanforderung wurde von einer Remoteclientanwendung übermittelt, jedoch werden keine der Verschlüsselungssammlungen, die von der Clientanwendung unterstützt werden, vom Server unterstützt. Fehler bei der SSL-Verbindungsanforderung.

Die aber ja anscheinend nur kosmetisch sind, wenn ich mir die diversen Threads dazu anschaue.

Ich habe aktuell absolut keinen Plan, woran es liegen könnte. Wir haben es jetzt mit zwei privaten VPN-Verbindungen getestet, über die eine Verbindung hat es geklappt über die andere nicht.
Über jeden Lösungsvorschlag wäre ich sehr dankbar!

Viele Grüße
Jimpiet