How to get off the Google Mail Blacklist

The Problem

I am running a web-site where customers can register and set up a personal account. Naturally, that requires emails to be sent from my server to the customers. A major problem was that Google Mail kept putting those emails in the spam folder of my customers. That was pretty annoying. Some customers complained and I could help them personally, but you never know how many of them simply gave up. Plus, the spam folder in Google Mail is quite difficult to find. I would not be astonished if many users of Google Mail don't even know about it. Google Mail is by far the most popular mail provider, so if it does not work with Google Mail, you simply lose a lot of potential customers. Very unsatisfying, but that's just how it is.

Why are mails placed in the spam folder?

I don't know. I have a dedicated IP address for my server, so that avoids all the problems of a shared server. My hoster is using a mail server FQDN which is different from my actual domain name for sending out emails. Both resolve to the same IP address. That could be something that was bugging Google Mail and made it believe all mails came from spammers.
 
There is nothing I can do about that. My hoster does not give me the opportunity to change any of that. And I do not want to miss the big advantages of a managed dedicated server. Certainly, I could set up my own root server and configure that differently, but I just don't want to deal with administering my own server.

The solution

What finally got me off the Google Mail black list was the following:

• Set up an SPF record (Sender Policy Framework) in my DNS, that explicitly allowed the mail server FQDN to send emails.
• Set up DKIM signatures for all my emails.

Here are a few resources that may help you with it:

• https://postmarkapp.com/blog/explaining-spf: Good introduction to SPF.
• http://www.openspf.org/SPF_Record_Syntax: Good overview of SPF record syntax.
• https://tools.ietf.org/html/rfc4871#page-50: Yeah, better have a look at the RFC of DKIM
• http://dkimvalidator.com: A great website for validating your DKIM and SPF setup. It gives you a temporary email address and validates all emails sent to that address. That was the most helpful tool in setting up everything.

Maybe your web application framework already comes with support for DKIM, then everything should be quite easy. You still need to be able to set up your own TXT-records in the DNS. In my case, I had to do everything from scratch, which took like two and a half hours. I don't know which of the two measures satisfied Google Mail, I didn't bother finding out. If I had to guess, I would say it is the signature.
 
This works like a charm. Google Mail is no longer placing the emails in the Spam Folder.