Google detects me as spam

I've been asked to look at some trouble I've been getting with our payrol system which is sending emails to our users. My problem is any email going through google (, etc) fails saying 'Our system has detected an unusual rate of 421-4.7.0 unsolicited mail'

The precise contents is (I've replaced the users email with USERSEMAIL, and our MYEXTERNALIP):-

Mar 18 08:25:49 ubuntusquid postfix/smtp[16132]: C86177A0AF8: to=<>,[]:25, delay=433182, delays=433176/0.04/3.5/2.3, dsn=4.7.0, status=deferred (host[] said: 421-4.7.0 [MYEXTERNALIP      15] Our system has detected an unusual rate of 421-4.7.0 unsolicited mail originating from your IP address. To protect our 421-4.7.0 users from spam, mail sent from your IP address has been temporarily 421-4.7.0 rate limited. Please visit 421-4.7.0 to review our Bulk 421 4.7.0 Email Senders Guidelines. fs8si24099257pdb.76 - gsmtp (in reply to end of DATA command))

I have gone through the link and done everything I can, but still getting the issue. Ive gone through forums, and done everything I can think of apart from things lile "dont send same subject" or "dont send encrypted attachments" but obviously I cant get around this with our payrol server.

Emails from the printers all seem fine to the users personal email address, so its only effecting the payrol emails, and they constantly fail even after several days of retrying.

Im using postfix on ubuntu server. Reverse DNS is setup correctly, and my IP and domains are not blocked on any spam lists.

Does anyone has any ideas how I can fix this going forward apart from us refusing to use users personal emails to google emails.
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Is the external IP being used by your payroll system also used by network clients? It's possible that there's an infected PC or server on your network sending out spam. My first step would be to block port 25 outbound on the firewall for all devices except those that you are sure are trusted, this will prevent any outbound mail from potentially infected clients and could, hopefully, resolve your issue.

Alternatively, if you have a bank of external IPs, ensure that your payroll system is assigned an address that isn't used by any other devices.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Email Servers

From novice to tech pro — start learning today.