Email is not this wonderful, democratic system of equals. Email is more like a school playground where a handful of enormous bullies control everything. You either learn to work with them, cater to their demands, or you'll never be able to visit large sections of the playground.
Gmail is relatively easy to appease, mostly just configuring your nameservers and email headers to Google's standards, then slowly building "reputation". Hotmail will block an entire domain (IP?) randomly every few years, then you fill out one of their infamous forms and pray they unblock you quickly. Yahoo (technically Verizon now) is even more difficult to work with, they block you out of nowhere and I've never figured out how to appeal. Seems like they do some kind of ratelimiting for smaller email servers, I don't know if it's some kind of punishment or just by default.
Then there's the dozen other major email providers. Some easy to work with, others not so much.
Do you mean SPF, DKIM and DMARC or something else? I will check the records again, just in case, but afaik they are perfect and Gmail still often classifies my mail as spam. It is annoying as hell (and your comparison to playground bullies is very apt).
Like you, I have properly set up DKIM and SPF and blah blah.
I also have a 12 year "clean" IP from he.net.
Sometimes gmail will mark something I send as spam that is, like yours, a reply to their user and is a recipient that I have a years long history of corresponding with.
That's frustrating but what really makes me angry is that there is no indication given that this occurs. Why can't google send a proper bounce or warning message ... or even an error code that I could at least see in my logs ?
In the arms race between spammers and (providers) are error indications exploited in some way ?
Or is google just being lazy ?
Relevant providers usually just require a few days of sending legit mail and occasionally asking to be unblocked, but there seems to be no chance getting into the inbox on GMail and Outlook with a "too low" sending volume.
If it wasn't for regulations, I would have already given up and switched to GMail.
Ah. But the million dollar question is WHERE did you run that server?
If you ran it off your home connection then there's your problem.
Pretty much everyone on the receiving end (ISPs, corporates etc.) will either block or assign a low reputation to home ISP IP ranges.
So basically you can do all the DKIM and SPF you like on your home MX server, but you're going to have the high hurdle of your untrustworthy IP range to fix first !
EDIT: Just saw you said "cheap Scaleway" ... well that's a similar sort of problem. Perceived "spammer friendly" hosts tend to be assigned a low rep in spam scanning. You won't be auto-blocked like residential IPs are, just a low rep set. (for any lawyers reading, I am NOT making any comment on Scaleway here, I am speaking in general terms !)
It's not a very good system.
At some point I just accepted reality and paid for a third party email server (Runbox) but the situation with the monopoly of these giants marking as spam anything they don't manage made just really sad.