Aparentemente, depois de alguns dias, ele começa a funcionar bem.
Neste momento, acho que o que realmente importa no GMAIL é passar nos testes:
SPF check: pass
DomainKeys check: neutral
DKIM check: pass
Sender-ID check: pass
SpamAssassin check: ham
E aguarde 3 ou 4 dias para que o Google possa atualizar seus servidores. Parece que o filtro de spam faz algum tipo de cache interno em DKIM
e SPF
pesquisas para um domínio específico.
ATUALIZAÇÃO: Esse problema parece estar de volta, não tenho ideia de como consertar isso.