It seems that, under certain conditions, GMail reports failed SPF checks for messages fetched via POP3 from other mail servers.
I noticed this behaviour on messages received, for example, by mail servers where an internal relay is used, like the following message sent from PayPal (which uses an hard-fail policy):
Delivered-To: MYSELF@gmail.com ... Received-SPF: fail (google.com: domain of xxxyyyzzz@emea.e.paypal.com does not designate A.B.C.D as permitted sender) client-ip=A.B.C.D; Received: by 10.64.225.172 with POP3 ... X-Gmail-Fetch-Info: MYSELF@MYDOMAIN.TLD 3 pop3.MYDOMAIN.TLD 995 MYSELF@MYDOMAIN.TLD Return-Path: <xxxyyyzzz@emea.e.paypal.com> Delivered-To: MYSELF@MYDOMAIN.TLD Received: from server1.MYPROVIDER.TLD (A.B.C.D) by server2.MYPROVIDER.TLD with SMTP; ... Received: from outbound.emea.e.paypal.com (96.47.30.179) by mx1.MYPROVIDER.TLD with SMTP; ... Return-Path: <xxxyyyzzz@emea.e.paypal.com> ... From: "PayPal" <paypal@e.paypal.it> To: MYSELF@MYDOMAIN.TLD