It turns out the problem sending email to gmail / google was some sort of change they’ve made on their end which has, in the words of Postfix creator Wietse Venema “screwed up their support for RFC 2920 command pipelining. “
This seems to have affected at the very least, anybody using Postfix 2.x as an MTA. More info, along with the fix see this post, if you’re running a postfix MTA you’ll need to do this until google fixes their system.
We’re in the process of updating our configs and the mail should resume momentarily. No mail was lost, no animals were harmed, everything was just deferred and will be dequeued starting….now.