So, hab mich dann doch mal mit SPF auseinander gesetzt. Klappt soweit erst mal, aber anscheinend versendet unser Hoster unter mehreren Adressen und war am Telefon nicht imstande, mir zu sagen auf welchen.
Ich hatte aus Mails den versendenden Mailserver rausgelesen und dementsprechend folgenden SPF-Eintrag angelegt:
TXT "v=spf1 a mx mx:mailserver -all"
Jetzt kommen vereinzelt Mails als failed zurück