Probaj ovo privremeno da postavis za SPF (obrati paznu da li je registrovao tu promenu - da nije izkesirao ...):
"v=spf1 a -all"
Generalno mi je malo sumljiv tvoj SPF ... A i ne vidim MX zapise u DNS?!!
Dalje, za testiranje probaj da posaljes na ove email adrese sto su naveli na sajtu
spf-test@openspf.org i
check-auth@verifier.port25.com ali direktno sa servera (npr upotrebom "mail" ili "mutt" shell komande ili iz probne PHP skripte - ne preko pop3 / imap).
Posalji header od poruke kako bi pogledao tacno sta je server odgovorio (ako nije problem) jer ovako neznam ko/sta ti je vratio ovo "It is impossible for us to say why it was rejected." ... Dobrodoslo bi i parce mail.log-a ...