As I said, it's totally opaque crapshot.
My current ISP, a local fiber provider, was not great getting going. Most of the IPs that they have are in at least 1 spam database, and it took a while for the ISP to reach out to the database maintainers themselves. Even then, since they're a small ISP, the IPs are still blacklisted. The ISP wasn't even a company when the IPs were added to these blacklists.
After a few months they were able to assign me an IP that wasn't in a blacklist somewhere. I still randomly have issues with the big providers though - gmail is probably the most annoying. Like dozzie, my SPF, DKIM, and DMARC setups are all valid.
Overall, I really enjoying running my own mail server. Every now and then there are a few annoyances, but it's worth it in the long run.
Why does Gmail hate my domain? | https://news.ycombinator.com/item?id=9855030
How to Avoid Spam Filters | https://news.ycombinator.com/item?id=10465639
Hotmail | https://news.ycombinator.com/item?id=14210939
ESP | https://news.ycombinator.com/item?id=14201704
If there are others I'd appreciate a link as I try to connect them!
I'd recommend trying http://dkimvalidator.com/ to make sure everything is perfect; having proper certs on your MXs seems to help too.
I run a pretty large email infra (~500k/minute) and I'd help you out if I can...
If you're still having problems with all that in place then why don't you just change IPs?
As for your help offer, thank you, but I'm good. It's usually other people who want to contact me, I rarely send the first message ever.
I mean.. If you get a solid result from dkimvalidator but google is still shitlisting you then I'd definitely consider moving to another host/dc/isp at least.
Depending on your size, it might be best just to make this someone else's problem (if you can) -- like google, o365, etc..
Maybe it's worse for non-English mail (maybe the statistical models are biased against "not English" even for people whom don't have English as a native language).
But I'm quite convinced google's (and to a lesser extent Hotmail/ms') "magic" spamfiltering is subtly (but annoyingly) broken.
I'm working on a guide for setting this stuff up; still WIP [1] -- feedback appreciated!
1: https://medium.com/@cyberpunk_networks/nsa-proof-your-email-...
Does this not happen when you send your emails to someone else? Mad props if everyone you email uses encryption!
How do you do that? The vast majority of blocklists I've interacted with have been unwilling to deal with questions, instead responding only that if you fix "something" (not always specified) automated measures will remove it from the list eventually.
In my experience it has also been extremely difficult to deal with people using blocklists. It's easy to find a bunch of people using .tor.dan.me.uk rather than .torexit.dan.me.uk "just to be safe". Frankly, I'm not sure why the former list exists in the first place other than to be an arse? What threats do entry/relay nodes pose to you?
Whenever one of our mailer IPs was blacklisted by one of the big targets (hotmail, gmail, etc) it would only be for 24hours after which I'd put it back into the pools (although, at least initially perhaps for our more reputable clients to warm it back up before letting the more dodgy stuff through it again). If you host your own NS's for the sender domains flipping SPF ips/ranges is not too hard (it's all automated for us, anyway).
The big boys work that way at least in my experience. I'm sure sometimes you'd hit a 'somedomain.foo' domain which is using a blocklist style thing that their (usually inexperienced) sysadmins think prevents them from receiving spam; but they're not worth arguing with. If you're doing email at volume shifting sends to another range for that client is usually 'enough' to get them through if they care that much about that one segment to ask you to do it.
If it's not then we'd usually refund instead of trying to negotiate with such admins.
Honestly though, blacklists have never been an issue for me and I've sent a ridiculous amount of email over the last 10 years...
You can always get it unlisted.
After that don't start to send hundred of email by day. You need to build a reputation for your domain and ip.
As the parent comment says, set up directly spf, dkim and dmarc (also arc if you can). Rspamd can help you do that.
I've been running a personal mail server for 5 years with simply following those rules.