O SPF e o DKIM não devem ser vistos como uma panacéia para problemas de entrega de e-mail. Período.
Dependendo de muitos fatores (fornecedor, software e outros ...), eles podem aumentar as chances de um bom resultado ou diminuir as chances de as mensagens serem devolvidas no nível do handshake SMTP, fornecer integridade ao remetente ou fazer com que os servidores de e-mail rejeitem spammers para vir do seu nome de domínio, e é isso. Também é importante saber que há remetentes com boa reputação de longa data que não usam essas duas técnicas (embora não usar SPF seja realmente estranho em 2017).
Eu diria que seu problema é bem conhecido - Por que o hotmail ainda rejeitar meus e-mails? . Com os detalhes que você forneceu, suspeito que o conteúdo das mensagens tenha algum significado para o software antispam que estão usando - talvez tente alterar o conteúdo e ver os resultados.