Google's gmail has recently started marking all mail from domain example.com (real domain name is hidden) as spam, with grey-box explanation of:
"Why is this message in spam? Lots of messages from example.com were identified as spam in the past."
also, messages to domains whose email is hosted on Google (AKA "G Suite"?) are generation bounces from firstname.lastname@example.org in the form of:
** Message not delivered **
There was a problem delivering your message to email@example.com. See the technical details below.
Learn more here: https://support.google.com/a/answer/168383
The response was:
Your email to group firstname.lastname@example.org was rejected due to spam classification.
The owner of the group can choose to enable message moderation instead of bouncing these emails.
More information can be found here: https://support.google.com/a/answer/168383.
Good facts are:
domain example.com does publish SPF, DKIM and DMARC records, and has valid FcRDNS
bounce messages from email@example.com also indicate SPF, DKIM and DMARC test are passed OK:
all of the email for domain example.com always originate from same SMTP server on IP X.X.X.X (which is correctly indicated in SPF record)
Received-SPF: pass (google.com: domain of firstname.lastname@example.org designates X.X.X.X as permitted sender) client-ip=X.X.X.X;
Authentication-Results: mx.google.com; dkim=pass email@example.com header.s=default header.b=eeWEtVgZ; spf=pass (google.com: domain of firstname.lastname@example.org designates X.X.X.X as permitted sender) email@example.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=example.com
outgoing SMTP traffic from X.X.X.X to google SMTP servers is TLS-encrypted (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256)
domain example.com and its SMTP server IPv4 address X.X.X.X are NOT on any of http://multirbl.valli.org RBL lists
E-mail firstname.lastname@example.org promptly deals with any problem, is on several FBL notification lists, and has not received any spam complaints in months.
domain example.com does not send any mass-mailings, and number of it's originated e-mails are quite low (few dozens emails per day at the most)
https://postmaster.google.com for domain example.com indicate User-reported spam rate of 0, no IP reputation, Authenticated traffic of 100% for SPF and DKIM success rate (but jumping from 0-100% for DMARC - for unknown reasons as that is static DNS record as are SPF/DKIM ones), 100% Inbound TLS Encryption rate, 0 delivery errors
other domains which share same SMTP server with IP X.X.X.X (and thus have same SPF, but different DKIM records) are unaffected by the issue, and can send mail normally to gmail.com users, without it being identified as a spam.
non-google based emails do not seem to have a problem with example.com emails
BAD facts are:
https://postmaster.google.com for domain example.com unfortunately also indicate "Domain reputation: Bad" (which is the worst on shown scale Bad, Low, Medium, High)
what seems to have caused a problem is that some of the users on example.com have set up their e-mail forwards from example.com mailboxes to their gmail.com private addresses. And as example.com domain does indeed receive a fair amount of spam (in the order of few hundred per day), all that has been forwarded for months to gmail (with envelope-from of example.com), which is probably what nuked the domain reputation to "bad" level.
the "forwarding spam to gmail" issue has been dealt with several days ago; and we have already asked several of gmail.com users to find e-mails in Spam folder and click on "Not spam" button and add senders to addressbook, but while that fixes the specific mail for specific gmail user, all mail from example.com to all other gmail users still continues to end up in spam folder with explanation that "Lots of messages from example.com were identified as spam in the past"
Question: what else can be done to improve e-mail domain reputation on google, so email will stop ending up in Spam folder because "lots of messages were identified as spam in the past"? Will just waiting cure the problem (and if so, any estimates how long before it gets better - especially if you've been in similar situation)? Any other hints what to try?