Nutzt Du IP V6?
Wenn nicht dann deaktiviere es in Postfix.
Nur um auszuschließen das die Sache nicht richtig funktioniert hat.
Du hast auch auf dem Server keine DNS-Einstellungen vorgenommen?
BTW...
Prüfe mal folgendes auf der Konsole
dig MX deineDomain.de