I have made contact with the people at Gmail who tell me that they use the first 64 bits of the 128-bit IPv6 address, not the first 32-bits as reported above. Nevertheless, they do recommend that for projects that send email to Gmail from a VPS (such as a [Linode][1], on which SQLite.org has run since 2004) should send email over IPv4, not IPv6. I thought I had done that. But apparently I didn't change the Postfix setting correctly. The correct fix is to run: postconf -e inet_protocol=ipv4 That has now been done and the mail logs do seem to show that outbound email is now always going over IPv4. For reference, to change this back, you set the inet_protocol value to "all". [1]: https://linode.com/ Hopefully this will resolve any lingering mail delivery problems. If you continue to have trouble, please post follow-ups.