Originally Posted by phinex
that we are missing on something, for example " including the ISP IP address in the record" ... or ?
That could be worth looking at. I had a case like that a while ago, where the isp had basically hijacked all emails so they came from their server. It caused spf authentication to fail.
I sorted it by looking at the email client settings (I think you said this was evolution) and changing it so they go directly to the mail server. I'm not sure if this applies in your case.
The problem with adding the isp ip address to your spf record is you're then authorising anyone with an email account on that server to send emails as you.
hope this helps.