I got flagged as spam pretty reliably by GMail, but I eventually discovered it was because my mail server was delivering mail to GMail over IPv6, and I had never set up proper records for my IPv6 addresses.
GMail was the only one I had that problem with because few mailservers are using IPv6.
Hmm does the 'mx' flag in SPF include the IPv6 addresses too?
The RFC seems to suggest it does but the website clearly says "All the A records for all the MX records":
http://www.openspf.org/SPF_Record_Syntax#mx
Gmail seems to accept mail from an IPv6 mx when the SPF record is "All the A records for all the MX records" (the headers says spf passed), but I'm not sure how others interpret it.
Is it better to explicitly list the IPv6 addresses in the SPF record?
I read him/her as referring to the mail server lacking an IPv6 reverse DNS address. This is a fairly common oversight, since IPv6 connectivity is getting more common, but many providers' control panels allow only easy self-setting of the IPv4 RDNS. Many mailservers are set up to reject mail from senders who lack an RDNS (and/or have one that doesn't forward-resolve back to the original IP), so in that situation, if you connect over IPv6 you may get rejected. The solution is to either disable IPv6 (less preferred option), or set a reverse DNS name for your IPv6 address (more preferred).
GMail was the only one I had that problem with because few mailservers are using IPv6.