The linode guys responded to my ticket. Apparently adding the site.com is a nono. They informed me that their DNS server automatically appends site.com and that having “_domainkey.site.com” messes it up.
So, I changed the entries from “_domainkey.site.com” to “_domainkey” and it worked properly.
This was not a big deal since the linode team responded so quickly – although this is counterintuitive because it relies on a specific unpublished feature of the linode DNS manager. I migrated over from Slicehost and their DNS servers most definitely require that your txt records be entered as “_domainkey.site.com”.
Ahh well. Thanks again.
This is how mine looks for the DKIM TXT entry:
Leave site.com out of the domainkey.
Name: should be selector._domainnkey
Value: should be the unquoted key=value pairs. This is not immediately clear from DKIM “install” instructions on various websites as they tell you it should be a single line record. Linode DNS manager abstracts this a bit, I guess.