Naja, prüfe mal welchen Hostnamen dein Server beim Senden verwendet und welcher Hostnamen im vom Server verwendeten Zertifikat steht.
Da soll es eine Abweichung geben. Wenn das stimmt, solltest Du das in der Tat korrigieren oder zumindest den SPF auf der Domain setzen, andernfalls werden immer mehr Server eure Mails nicht mehr akzeptieren.