Och, kann so einiges sein:
Für den Mailserver wurde ein Hostname des Server-Anbieters anstatt einer korrekten FQDN verwendet
Kaputtes DNS
Kein SPF oder DKIM
Kaputtes Mailserverzertifikat
Server-IP ist auf Spammer-Blocklist
Einfach mal ein paar Toosl anwerfen:
mxtoolbox.com
Free multiple DNSBL/RBL lookup and FCrDNS check tool. Test the IP (IPv4 or IPv6) of your mailserver on more than 200 blacklists and whitelists.
multirbl.valli.org
SPF record and DKIM check
www.mail-tester.com