Every couple of months, Gmail starts depositing any email from my users into spam. No warning, no rejection, just a vague yellow banner on the recipient's view that says "this message has the characteristics of spam." The message could be in plain text with no links, still the same. I have SPF, DKIM, and rDNS all configured. I send from a single IPv4 and single IPv6 address with matching records. No RBL entries. Even the headers on a "spam" message say that everything passes and is fine.
Oh, and it isn't a domain reputation problem: only one of the domains I host even has a web site and all of them are at least five years old. Two of my domains predate Google itself. :P
The real kicker? I can't use their postmaster site, either. Why? We don't generate enough email to rank a report!
Meanwhile, no problems at all from any other receiving hosts. I have to log into several Gmail accounts and click "this is not spam" on some test messages and then it is fine for another 50 days. After that, back to the bit bucket.
Grr.
I have this problem sending through:
* An email service such as Mailchimp
* My own server with SPF / DKIM and good reputation / deliverability for other domains
* Amazon AWS Simple Email Service
I think it is something on the domain level – perhaps they've flagged the domain.