Why is my email failing Gmail's DKIM test?

Your SPF record isn't affecting this.

By the looks of it, you have a DMARC record set up, and you are not signing outgoing mail with DKIM. To remedy the problem, either sign the outgoing mail, or remove the DMARC policy.

The DMARC record is a TXT record like the SPF record, but it is at _dmarc.example.net where example.net is your domain. If you don't think you have one or you don't want to remove it, change it to v=DMARC1; p=none to null it out.

Alternatively, since you are using SPF, I see you may not want to do this. In this case, leave your _dmarc record as it is, but you will have to get rid of or change your _domainkeys record.

DKIM specifies that for a domain example.net, the DKIM record will be queried IN TXT _domainkeys.example.net. You must find this record and either remove it, or add the t=y flag to specify that (as you are ostensibly testing DKIM) the results of DKIM verification should be ignored. Also, ensure your _dmarc record does not contain the adkim tag, and particularly not adkim=s.

Your data is obfuscated which makes helping you difficult. I see a number of problems:

• If you haven't obfuscated your IP address, your DNS passes rDNS validation but looks very much like a spambot. Try getting server.example.com setup as the PTR for your address and add server.example.com to your DNS. Getting the PTR record setup requires support of your IP address provider (usually your ISP). You need a fixed IP address for this.
• Your server doesn't seem to know who it is. It should give server.example.com as its name in the HELO or ELHO request.
• You mail isn't DKIM signed. DMARC does not require DKIM, but your policy must match your practice.

Try sending an email to [email protected] (reported no longer in service) to see how well your server is configured. Other options are listed in my article on Detecting Email Server Forgery.

If your domain does not have DKIM set, you definitely do not need DKIM set up. Its absence would not cause GMail to throw your e-mail to SPAM. Its presence might increase its SPAM rating so it would not be rejected.

To check your SPF, you need to tell us your domain and IP addresses of your SMTP server. Or, you can use online check tools on http://www.openspf.org/.

To understand DMARC, check this: http://support.google.com/a/bin/answer.py?hl=en&answer=2466580.