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!
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.