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?