Eu descobri o motivo (com a ajuda dos caras gentis da lista de discussão do opendkim):
No meu arquivo opendkim.conf eu tinha apenas o campo
AlwaysSignHeaders From,Sender,To,CC,Subject,Message-Id,Date
especificado. Descobriu-se que você precisa adicionar o campo SignHeaders também, então agora a configuração se parece com:
...
SignHeaders From,Sender,To,CC,Subject,Message-Id,Date
AlwaysSignHeaders From,Sender,To,CC,Subject,Message-Id,Date
...
é isso.
Editar:
O pessoal da opendkim observou que AlwaysSignHeaders está obsoleto, OversignHeaders deve ser usado em seu lugar.