Não consigo falar com o DKIM, mas parece que você não tem nenhum registro SPF:
[me@risby ~]$ dig txt chvw.de
; <<>> DiG 9.8.3-P3-RedHat-9.8.3-4.P3.fc16 <<>> txt chvw.de
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 64092
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0
;; QUESTION SECTION:
;chvw.de. IN TXT
;; AUTHORITY SECTION:
chvw.de. 10631 IN SOA bob.ns.cloudflare.com. dns.cloudflare.com. 2012092713 10000 2400 604800 3600
Então, quando você diz que ativou o SPF, o que exatamente você fez? Começar a trabalhar com registros SPF seria definitivamente um bom começo.