The trick with the SPF Record

With Sender Policy Framework (SPF) Records, one can specify which hosts are authentic senders of email on behalf of the domain.

But SPF Records can be tricky if you're using multiple hosts for sending mails (for instance, when all the mails are handled by Google apps but you still use your id to send mails from the server).

Correct me if I'm wrong here, but this seems to work out fine for SPF record for setups like the ones mentioned above:

v=spf1 a mx include:aspmx.googlemail.com ~all

a corresponds to the actual host that the A record points to. mx corresponds to the hosts designated to handle email. And to be on the safer side, the include:aspmx.googlemail.com option. ~ takes care not to be too strict with this and soft fails would still get through.

And the test script for SPF record confirms the record to be valid.