GMail is arbitrarily blocking ip addresses or subnets and there's nothing you can do about it.
One year ago I've purchased a VPS with a clean IP address (checked against all DNSBLs), set up mail server with SMTP and IMAP server, set up SPF, DKIM and DMARC and was able to successfully send emails to Gmail for 3 months.
After 3 months GMail stopped accepting mail from my server saying that my ip address was used to send spam. I'm pretty much sure it wasn't me. My VPS OS and mail server are up to date, there was no suspicious activity in the logs, so it's very unlikely that I was hacked.
There're only three possible explanations for it: 1. My VPS was hacked indeed 2. Some bad guy from the same IP network sent spam (although GMail error message specifically states that spam was sent by this exact IP address, not an address from the same network). 3. GMail just randomly blocks access to any little guy trying to setup independent mail server just because they can.
I'll never know the truth but it was very disappointing experience. Also, lost couple of semi-important emails this way.
Association extends to sharing an IP allocation. It may even extend to sharing a nameserver. Gmail isn’t randomly targeting a “little guy” for the Internet Death Penalty. This isn’t arbitrary, and an entitled victim mindset isn’t going to get your email delivered.
Like I said, prefer IPv6. For now at least, bad senders don’t choose it. That’s the something you can do about it. Pro tip: most VPS services are a swamp.
Incidentally, if your server was rooted, don’t assume that this would show up in the mail logs. There are plenty other ways to use a compromised host as an open relay, including lying to your admin tools.
Ultimately, I think that if you’re unwilling or unable to run a MTA to the maximum level of reputation, then skip doing so, and use Postmark instead.
This is the most likely situation. If a VPS provider is sufficiently cheap, it will attract the wrong people, who will then get the entire VPS provider's IP blocks blacklisted.
It's a shame, but it's the reality. There are lots of discussions around this subject on various mailing lists, where people from the likes of Gmail have chimed in stating as much.
I would reckon it takes as little as 10% of the addresses in a /24 (so ~25 IPs) to get that entire netblock blacklisted.
If you want a higher probability of clean IPs, you need to be using a provider that is sufficiently expensive to not attract spammers.
Either that, or you need your own IPs.
Or just use IPv6, which will probably fix this.
It’s no surprise that Gmail et al are more interested in sender domain reputation, and also the graph of related domains, than they were a few years ago.
I've been running mail servers on OVH (which is known to be a cheap host) for years and I successfully deliver to GMail and other providers without any issues. I'm pretty sure delivering over IPv6 also helps a lot since spammers will never bother setting that up.
I use separate sender domains for a newsletter than for transactional mail.
You can monitor reputation with Gmail and Outlook postmaster tools, and there are various sites that will mass query RBLs; worth checking occasionally. I have a monthly reminder in the calendar. Sign up for the JMRP and SNDS.
Then just behave like a responsible sender. Don’t send unsolicited mail. Make it easy to unsubscribe, with RFC8085 headers and easily found unsubscribe links. Honour unsubscribes instantly. Honour spam reports instantly with a suppression list. Make the first statement of your communication one that describes the purpose; the second, the unsubscribe link. Make it easier, both functionally and emotionally, for recipients to unsubscribe rather than to report you as junk.
Run your emails through SpamAssassin before sending, and respect and understand the scoring. Read the Gmail sender guidelines (https://support.google.com/mail/answer/81126), they are good advice.
Include a plain text part.
Do not trust anyone claiming you can pay to improve reputation. That is snake oil.