Ok, eu descobri o porquê. Foi porque eu estava enviando e-mail com um endereço diferente do meu domínio. Depois que mudei o endereço de para um endereço para [email protected], ele começou a assiná-los.
Isso é óbvio em retrospectiva, já que eu acho que é isso que as chaves de domínio fazem, é assinar o do domínio. Por alguma razão eu supus que estava assinando com base no caminho de retorno ou no IP do servidor de e-mail, e não no endereço de saída.
Como estou criando um ESP (provedor de serviços de e-mail), preciso enviar e-mails de vários domínios. Então, meu próximo desafio é fazer com que ele seja assinado para todos os domínios.
Edit: Solução publicada aqui DKIM assina correio de saída de qualquer domínio ( com o Postfix e Ubuntu)