Nu vet jag inte om det beror på på SPF, men du bör ändå lägga in det i din dns.
Lägg in som TXT 
	Citat:
	
	
		| "v=spf1 a mx include:_spf.google.com -all" | 
	
  inklusive citat-tecknen i DNS-en.
Detta säger att de servrar du angett som a-record, mx-record samt _spf.google.com har rätt att skicka mail från din domän.
Du kan läsa mer på 
http://www.openspf.org/Introduction