Just chiming in :)
We have been seeing a lot of this lately too. Here is what I have been telling our customers...
Google and other large ESPs are really cracking down on the email they accept. We have determined that the best thing to do in this situation is the following…
1. Check to ensure that your users are not forwarding spam to their own external accounts. We are aware that many users (ours too) forward their mail from our mail servers to Gmail or Yahoo for example. The problem is, if the domain is not set up to not forward the spam too, all of the spam gets forwarded with the good mail and it looks like our server is spamming Gmail’s servers.
2. Be sure that you do not have any compromised accounts that could be shooting spam out. Put prevention for this in place such as Declude Hijack, SM Throttling, SM Internal Spammer Notification.
3. Ensure you have proper SPF, DKIM, and DMARC records set up for all of your domains.
4. Have SSL/TLS in place for all of your domains and that you are using the secure ports in your email clients to send mail
5. Ensure you have proper reverse DNS set up for all of your server IPs
6.) Ensure you have a proper HELO set up for each of your domains
7.) Sign up for Google’s Postmaster Tools and verify all of your domains.
I hope this helps someone out there!
Linda Pagillo
Mail's Best Friend
Email: linda.pagillo@mailsbestfriend.com
Web: www.mailsbestfriend.com
Authorized SmarterTools Reseller
Authorized Message Sniffer Reseller