Google, your IPv6-related email restrictions suck. Amen, I recently got bit by this with a new Linode instance (they assign IPv6 to their servers, which is great until you run into this.) There seems to be an easy fix with Postfix: Fixing Google's new IPv6 mail policy with Postfix and for Sendmail I had to add a line from here: How to stop Sendmail sending mail from IPv6 instead of IPv4.
e.g. if your IPv4 address is 126.96.36.199, specify:
It's especially frustrating because I do have a reverse PTR record, it was required to be able to send to Comcast. While Comcast seems ok with it Google just flat refuses mail no matter what I do.