DKIM Will be the End of Me

I have a VPS that I had a fresh install of CentOS 6 on it and then I installed virtualmin on it and we’ve been great for a few months. I’ve been hosting a handful of domains from there and on one of the domains in particular, I’m going to need to send out email (and not go to spam).

The domain I’m trying to fix is

I have both my hosting DNS and server DNS mirrored (to the best that I can). My domains are using the nameservers on the hosting DNS.

I created an TXT record for my SPF that was generated from the SPF Wizard on Microsoft on my hosting platform. I also followed the instructions provided in the Virtualmin documentation to install a domain key and the installation ran without any error and I followed the directions correctly. I copied that domain key and created a TXT record on my hosting DNS as well.

So I’ve been testing my stuff to see if it goes straight to spam and it does… so I looked online and ran a couple checks.
Half the time this says I don’t have an SPF record and the other half it says its fine.
It says Domain-Key Status: NOT PASSED, The message does have have a domain key, but i have the following header displayed below…

DKIM-Signature: my domain key
This says a couple things.
DomainKeys Information:

Message does not contain a DomainKeys Signature

but then it says this further down…

DKIM Information:
DKIM Signature
Message contains this DKIM Signature:
DKIM-Signature: … *my dkim *

Validating Signature
result = invalid
Details: public key: OpenSSL error: bad base64 decode

SPF records pass on this test as well.

I’m honestly not sure what to try at this point. I stopped/restarted dkim-milter and restarted postfix to no avail. I have an SSL on that IP (and domain in fact) but I still get that error. I updated all the packages I could so I’m as up to date as possible. Can someone help direct me on what steps I should take for things to check or what to do next? Thanks everyone.
On this site, half the time it says there are no records, but if I keep hitting the check button, it will popup with the record that says it can’t parse the value of the record so it doesn’t know if it’s working or not.

We had the same issue with one server. Turned out the team found that Virtualmin was configure properly. But the DNS DKIM TXT records with the VPS host was not. If you do not use Virtualmin DNS BIND server. But instead use your VPS host DNS server. Have you tried contacting your VPS host asking what format they need for their DNS DKIM record? Often VPS hosts have a specific format they need for their DNS DKIM / TXT records. In our case we needed to reformat it so they recognize it. Such as with or without quotes, with or without white spaces, and such.

Another thing to consider is the TTL. Depending on your configuration, any changes might take anywhere from 5 minutes to 2 days to take effect and propagate through the web. Using Virtualmin BIND or with most VPS DNS tool, you can change those TTL duration to your liking.

Related documentation at