Google Apps, SPF, softfail problem (validates with validation tools, but still softfails otherwise)

I guess this is probably a commonly asked and boring question but I'm really at a loss and I don't know what else to do. This might be a duplicate of other questions, but none of the solutions worked for me. I've Googled around and read just about anything I could find but I'm still puzzled as to why it doesn't work.

The gist of my problem is that I have set-up Google Apps for a client of mine with the domain fintan.dk. Everthing works just excellent, except emails sent from *@fintan.dk (either with the Gmail web-interface or desktop client) to a non-Google Apps email gets a softfail (I have sent to my University email, an email hosted at MediaTemple and even Hotmail). The emails gets a pass when sent to a Google Apps or Gmail address though... (All emails from that domain are sent via email clients.)

So this is what I have done so far:

• I've added the SPF record Google recommended (v=spf1 include:_spf.google.com ~all), waited several days hoping it would a DNS update delay problem. Now, three days later there is no change.
• I have verified the settings in the desktop clients several times.
• I have validated the records with validation tools like the SPF Query Tool, [email protected] and [email protected]. All of them validate and gives a pass, saying there shouldn't be a problem, but strangely there still is.

So, I really don't know what else to do. Any help is very much appreciated.

Thank you in advance!

--

Here are som headers for an email I sent from a *@fintan.dk address to a non-Google Apps/-Gmail address with email hosted at MediaTemple, **@newzoo.no.

Delivered-To: ***@***
Received: by 10.204.113.141 with SMTP id a13cs215458bkq;
        Mon, 7 Jun 2010 14:27:23 -0700 (PDT)
Received: by 10.204.83.228 with SMTP id g36mr347934bkl.133.1275946041770;
        Mon, 07 Jun 2010 14:27:21 -0700 (PDT)
Received-SPF: softfail (google.com: best guess record for domain of transitioning **@fintan.dk does not designate **.**.***.*** as permitted sender) client-ip=**.**.***.***;
Received: by 10.188.26.13 with POP3 id 13mf159579bwz.53;
        Mon, 07 Jun 2010 14:27:21 -0700 (PDT)
X-Gmail-Fetch-Info: **@newzoo.no 3 mail.newzoo.no 110 **@newzoo.no
Return-path: <**@fintan.dk>
Envelope-to: **@newzoo.no
Delivery-date: Mon, 07 Jun 2010 14:27:17 -0700
Received: from mail-ew0-f224.google.com ([209.85.219.224]:44843)
    by cl29.gs01.gridserver.com with esmtp (Exim 4.63)
    (envelope-from <**@fintan.dk>)
    id 1OLjqk-0007P1-RP
    for [email protected]; Mon, 07 Jun 2010 14:27:17 -0700
Received: by ewy24 with SMTP id 24so1953534ewy.34
        for <**@newzoo.no>; Mon, 07 Jun 2010 14:27:13 -0700 (PDT)
Received: by 10.213.22.14 with SMTP id l14mr11377870ebb.55.1275946032661;
        Mon, 07 Jun 2010 14:27:12 -0700 (PDT)
Received: from [192.168.1.4] (cm-84.215.178.166.getinternet.no [84.215.178.166])
        by mx.google.com with ESMTPS id 13sm2910690ewy.5.2010.06.07.14.27.11
        (version=TLSv1/SSLv3 cipher=RC4-MD5);
        Mon, 07 Jun 2010 14:27:11 -0700 (PDT)
From: Moquan Chen <**@fintan.dk>
Content-Type: multipart/alternative; boundary=Apple-Mail-16--861396158
Date: Mon, 7 Jun 2010 23:27:10 +0200
References: <****[email protected]>
To: **@newzoo.no
Message-Id: <[email protected]>
Mime-Version: 1.0 (Apple Message framework v1075.2)
X-Mailer: Apple Mail (2.1075.2)
X-Spam-Status: "score=1.0 tests=HTML_MESSAGE version=3.1.7"
X-Spam-Level: *

Solution 1:

Try changing your record from v=spf1 include:_spf.google.com ~all to v=spf1 mx include:_spf.google.com ~all

Thats what my SPF record has (note the mx addition) it should work since google's servers are the MX servers for the domain.

Also if you need the server that hosts the fintan.dk website to send emails change the record to v=spf1 a mx include:_spf.google.com ~all