Ach so: eine Änderung hatte ich im DNS eingetragen: Als MX habe ich mit geringerer Prio den tatsächlichen rDNS eingetragen. Keine Ahnung, ob das geholfen hat.