What's wrong with my SPF?

When I receive an email on Google from my domain ("mail.gramma.ro") I see this in the headers:

Received-SPF: softfail (google.com: best guess record for domain of transitioning [email protected] does not designate 213.133.103.5 as permitted sender) client-ip=213.133.103.5;

My SPF is defined as:

v=spf1 a mx ~all

Can you please tell me why Google sees it with softfail status?

Looks valid. Try specifying the IP address though as that takes out a level of possible failure.

v=spf1 a mx ip4:213.133.103.5 ~all

EDIT

I'll clarify. I'm NOT saying that this should be a permanent solution. This is enough to get things working (and email flowing) until the real problem can be found.

Based on your A and MX records (as reported at www.dnsstuff.com) and based on the SPF record, I can't tell why it's failing but I can tell you that ~all tells Google to treat it as a soft failure.

EDIT

It's probably a DNS lookup problem. The name servers for your domain as listed by your name servers are:

gramma.ro

ns.gramma.ro

But the name servers listed at the parent servers are:

ns.gramma.ro

This is probably causing some name resolution problems for you.

Your record looks to be set correctly (MX resolves back to mail.gramma.ro which resolves to 213.133.103.5), but Google is using "best guess" instead of the actual specified record.

It's likely that you sent this test message too soon after setting up the record, and the Google servers didn't get the record at all when this check occurred. Try sending a new test message.