Gestern am späten Nachmittag habe ich Antwort vom netcup Support bekommen.
Der Reverse DNS Eintrag wurde wie von uns gewünscht auf "mail.betterinter.net" geändert und wird auch korrekt im HELO / EHLO verwendet (wäre ja auch noch ein Problemchen gewesen).
Bei allen Domains auf diesem Server habe ich den MX-Eintrag auf diesen neuen DNS-Eintrag umgestellt und GMX und WEB.DE nehmen die Mails jetzt problemlos an.
Fazit: Das Problem wurde mit der Abänderung des Standard Reverse DNS Eintrags gelöst.
Aus meiner Sicht sollte netcup unbedingt die Möglichkeit schaffen, dass Kunden bei allen Servern den Standard Eintrag ändern können. Es wäre sogar angeraten, dass netcup Kunden, die den Mail-Service aktiviert haben, darauf hinweist, dass eine Änderung dringend angeraten ist wenn man keine Probleme mit Empfängern bei GMX, WEB.DE, etc haben will.
Martin