Jeg har ikke adgang til den mailserver, desværre.
Men jeg har fundet ud af det, så undskyld ulejligheden.
Problemet var, at når jeg sendte mails via php, stod følgende i headeren:
Received: from sc-027.rackhost.dk (fafdifh.dk. [195.140.135.254])
Og når google så skulle lave SPF lookup i dns, kiggede den efter sc-027.rackhost.dk og den findes altså ikke

Har rettet, så der nu står
Received: from fafdifh.dk (fafdifh.dk. [195.140.135.254])
Og så virker det...