Gmail SPF fail based on client IP

First, pull the spf record of example.com:

$ dig -t spf mail.example.com

Verify that example.com is on the senders list. Your spf record should look something like this:

"v=spf1 a:mail.example.com a:cname.example.com -all"

Take any domain names listed and do a DNS lookup on them to get the IP addresses:

$ dig mail.example.com

Then do a PTR look up to get the reverse DNS name for the IP:

$ dig -x XX.XX.XX.XX

The reverse IP lookup should match one of the records listed in the spf record. It would be helpful to start with the spf record though so we can see what's going on.

Yes, Google would be correct in identifying the SPF failure. The IP address that should be checked is the address that is connecting to Google's mail server. As there is no received header for Google, I suspect your mail server is checking SPF on the connection. It should only check SPF for unauthenticated connections from the Internet. Local connections and authenticated connections should bypass SPF validation.

SPF is intended to ensure the sending computer is permitted by the sending domain. Normally a domain would have 1 or 2 mail servers that handle all emails sent to or received from the Internet. These addresses should be the ones listed in the SPF record for the domain.

In this case, johndoe appears to be connecting to the domain's mail server. If the server is not on the domain's network, it is common to use an authenticated connection on the submission port (587). The mail server should then forward the message to Gmail and SPF should pass. If SPF still fails, the SPF record needs to be corrected to include IP of the mail server. There are several mechanisms that can be used.

My Email Policy ensures that all legitimate mail sent from my domain will pass SPF. There are some services that forward messages on behalf of my users which will fail SPF. However, the recorded failures I have received from servers validating DMARC have all been spammers.