А они должны? Вы путаете с сертификатами, т.к. ключи не могут быть «самоподписанные».
Приватный ключи используется для подписи сообщения, третьи системы используют публичный ключ для проверки подписи.
Эм… ЧЯДНТ? Я не могу найти у гугла TXT запись adsp. dig TXT _adsp._domainkey.gmail-smtp-in.l.google.com.
dig TXT _adsp._domainkey.google.com.
dig TXT _adsp._domainkey.gmail.com.
Нету такой записи.
Exim + DKIM на примере FreeBSD 8.2