Sender Policy Framework is a minor attempt to help identify SPAM in email by using a DNS record(s) to say which mail servers are allowed to send email on behalf of the domain. In my case, I forward all mail via one of our GMail accounts from web servers and although I had an SPF entry in my DNS, I noticed that GMail was reporting the email as:

Received-SPF: neutral (google.com: 209.85.215.178 is neither permitted nor denied by best guess record for domain of user@mydomain.co.uk) client-ip=209.85.215.178;
 
I was slightly surprised because I had just assumed this worked and didn't really understand how SPF was supposed to work, especially the weird Google code I had to add to the DNS entry. It took a while initially to learn what exactly is going on but it is pretty simple. On receiving an email from a user@domain, the receiving email server checks to see if the DNS for that domain has an SPF record. This record contains one or more IP addresses that are permitted to relay mail for that domain, this results in one of several things happening: 1) If the IP of the sending mail server is in the record, it passes and the message changes to:
 
Received-SPF: pass (google.com: domain of user@mydomain.co.uk designates 209.85.212.179 as permitted sender) client-ip=209.85.212.179;
 
2) If the address is NOT in the SPF record then depending on the flag at the end of the SPF record, one of two things will happen. If the record contains ~all, then the system will produce a soft fail, an indication that there might be something wrong with the email but maybe it's OK. Google have sometimes suggested this because otherwise any temporary problems with the DNS system might otherwise flag good emails as SPAM. If the flag is -all, then a hard fail will be produced which in many email programs will immediately flag the message as SPAM.
3) If the receiving mail server cannot find an SPF record, the result will be neutral as per the first message above and the receiving client basically won't have any way to mark the message as SPAM other than the usual weird rules they might apply to content and style of the email.

Anyway, none of this was working as expected, despite using Google's standard entry of "v=spf1 include:_spf.google.com ~all" in my DNS SPF record. Fortunately, I eventually found the answer in this blog post: http://aahank.com/2013/google-apps-with-amazon-route-53/

The piece I was missing was that I needed a TXT record as well as the SPF record. SPF sounds more correct and perhaps some servers look-up the SPF record but obviously GMail uses the TXT one. By adding the TXT record (with the same content as the SPF record), in no time, GMail was correctly identifying my emails as genuine. Hopefully this will help in any SPAM problems in the future!