google verweigert Mails

[Andre]

Nabend,

es geht um Mails, die über unseren Mailserver weitergeleitet werden.
Die meisten Mails kommen sauber durch.

Doch bei machen (mehrere am Tag) meldet google:

relay=gmail-smtp-in.l.google.com[XX.XX.XX.XX]:25, delay=0.36, 
delays=0/0.01/0.08/0.26, dsn=5.0.0, status=bounced (host 
gmail-smtp-in.l.google.com[xx.xx.xx.xx] said: 421-4.7.28 15 Our system 
has detected an unusual rate of 421-4.7.28 unsolicited mail originating 
from your IP address. To protect our 500 5.0.0 google anti spam (in 
reply to end of DATA command))

Im Log sind keine Aktivitäten erkennbar, die auf Spamversand hindeuten.

Allerdings sind kommen viele E-Mails (mehrere Hundert am Tag), die über 
unser Mailsystem weitergeleitet werden, nicht durch:

: to=<empfänger at gmail.com>, relay=gmail-smtp-in.l.google.com:25, 
delay=0.73, delays=0/0/0.09/0.64, dsn=5.7.26, status=bounced (host 
gmail-smtp-in.l.google.com said: 550-5.7.26 The MAIL FROM domain 
[domain.com] has an SPF record with a 550-5.7.26 hard fail policy (-all) 
but it fails to pass SPF checks with the ip: 550-5.7.26 [xx.xx.xx.xx]. 
To best protect our users from spam and phishing, 550-5.7.26 the message 
has been blocked. Please visit 550-5.7.26 
https://support.google.com/mail/answer/81126#authentication for more 550 
5.7.26 information. 
d17-20020a05640208d100b005163b432853si10663044edz.487 - gsmtp (in reply 
to end of DATA command))

Unser Mailsystem ist korrekt eingerichtet und funktioniert unverändert 
seit Jahren. Das Problem mit Gmail scheint neu zu sein. Es sieht so aus, 
dass google nun solche Mails als Spam wertet.

Wenn bei dem Absendersystem "-all" eingerichtet ist, dann ist doch klar, 
dass wir jetzt nicht weiterleiten können.

Mail-From umschreiben wird, soweit mir bekannt ist, nicht empfohlen.
Das wäre aber, wenn ich es richtig technisch verstehe, die einzige 
Lösung, oder?

Wie habt ihr denn das Problem gelöst?

--
LG
Andre