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