Hi,
die DNS-Einträge sind meiner Meinung nach ok. Wahrscheinlich kommen die Mails nicht an wegen Spamfilter-Einstellungen des anderen Anbieters?
Eventuell hilft es, die Anbieter zu Kontaktieren ... Bei GMX gibt es z. B. den "Postmaster Support" mit einigen Informationen.
So doof wie es klingt, ich mag die Verbiegerei auch nicht und bei mir war es auch ein Steiniger weg, die Mailzustellung endlich zuverlässig zu machen.
DNS-Whitelist, DKIM und DMARC können helfen, erfordern aber auch einigen Aufwand.
Schau Dir auch einmal das "MX Lookup Tool" (Suchmaschine deiner Wahl) an.
Viele Grüße
Moppi