I've had a similar problem in the past, now fixed.
Based on my experience, just an extra suggestion that I haven't seen mentioned thus far. Using DKIM signing might help as well --- as long as over time Google and other ISPs can learn that your signature is associated to a good reputation.

"apt-get install opendkim" is your friend