Mails kommen stark verzögert bzw. gar nicht an

Hallo an alle.

Ich habe folgendes Problem:

Ein Kunde bekommt einige Mails entweder stark verzögert (2-4 Tage) bzw. gar nicht.
Dies betrifft allerdings (derzeit) nur Absender von einigen (!) ausländischen Domains.

Die Mails, die nicht ankommen werden im Mailmanager der Firewall auch nicht angezeigt
(weder im SMTP LOG noch in der Quarantaine). Sie kommen wirklich einfach nicht an.

Testmails innerhalb von .de gar kein Problem.

Ausgehende Mails kein Problem

Kontrolle der Domaine auf Blacklisting: negativ

Zur Umgebung:
Sophos UTM als Mailgateway
Interner Exchange
ISP alt: Vodafone
ISP neue: Kabel BW
Domain: 1&1

Wichtige Info:
Demnächst wird der Internetprovider umngestellt.
-->Neue Feste IPs
-->Neue MX Einträge auf die Sophos
Das bedeutet, ich habe vorab schon neue MX Einträge in den Zonefiles erstellt,
diese aber von der Priorität niedriger als die alten MX Einträge bewertet.
D.h. ich kann bei der Umstellung demnächst einfach die Gewichtung der Einträge
ändern und könnte im Fehlerfall wieder zurückschwenken.
(Diese Aktion habe ich nur machen müssen, damit ich bei Kabel BW den neuen Pointer für das Reverse-Lookup beantragen konnte)

Ansatz:

Exchange: Spielt glaube ich bei dem Problem keine Rolle, da die Mails ja von der
Sophos direkt weitergegeben werden und gut.

Sophos: Laut den Logs bekommt diese die Mails halt erst zu dem entsprechendem
Zeitpunkt. Für die meisten Domains funktioniert der Traffic soweit ja auch.

MX: Hier sehe ich eine mögliche Fehlerquelle, aber der großteil des Mailverkehrs funktioniert ja.
Außerdem waren die Einträge bzgl. MX schon vor 3-4 Wochen (Die Umstellung hätte schon lange
passiert sein sollen, wurde aber verschoben) und die Probleme bestehen erst seit 3 Tagen.

Hat irgend jemand eine Idee für mich?

Danke im voraus.