Hmm well, I've found it to be pretty straightforward, I'm curious why this is happening to you though and there must be a solution...
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..
The real problem is Google is opaque in dropping such mail in recipients spam folder. Hotmail can sometimes be annoying in this regard too. As far as I've managed neither does the sane thing and add a header that report on how they've divided that "this mail is spam" - so the recipient doesn't have anything to go on either, other than hoping "mark this as bot spam/add to address book/send email/reply to address" help Google/Ms treat it as "not spam".
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 definitely not giving to somebody else my /var/log/mail.log, IMAP/Mutt
access, sieve rules, nor ad hoc dedicated aliases for every website account
I create. And on top of that, I would land on some US-based server for ease of
illegal spying and my mail would be harvested for some advertising crap, all
to solve something that is not a problem for me. Not happening.
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?