Das mit rDNS reicht leider nicht aus. Ich zitiere den Text von T-Online (siehe oben vom TE):
ZitatInsbesondere empfehlen wir, den Hostnamen so zu wählen, dass seine
| Nutzung als Mailserver für Außenstehende erkennbar ist (z. B.
| mail.example.com), und >>> sicherzustellen, dass die Domain zu einer
| Website führt, die eine Anbieterkennzeichnung mit sämtlichen
| Kontaktdaten beinhaltet. <<<
Das heißt: Die wollen, dass unter der Domain zwingend eine Webseite mit einem Impressum zu finden ist. Habe schon mit denen von T-Online eine heftige Diskussion geführt. Die wissen nicht, und halten die RFCs zu unsicher. Mir ist das zu blöd, da ich als Privatperson nicht verpflichtet bin, meine Daten ins Internet zu posaunen. Als Workaround habe ich meinen Mailserver so konfiguriert, dass die Mails, die an @t-online.de adressiert sind, automatisch an SMTP-Relay (in diesem Fall nutze ich den Dienst "mailjet" wegen DSVGO) versendet werden. Die schicken dann wiederum weiter an T-Online. Geht wunderbar mit DKIM und SPF, nichts wird im Header kaputtgemacht.
Die Anleitung ist hier. Dazu einfach unter "/etc/postfix/transport" eine Zeile einfügen: t-online.de smtp:smtp-relay.xxxx.com:587