Well, I might tend to agree ... I was simply mentioning that a blocked port 25 doesn't necessarily mean you have to start running an SSL-enabled MTA; there are plenty of ways to get around it (or, at least, I can name two).
You might be right about SPF lookups; since the OP doesn't give us him actual domain name (which is OK, I suppose), we can't actually do anything but speculate on that, however.
One of my actions in tracking down this real issue would be to SSH in to my server (assuming it was me and my server having the problem) and run an SMTP session over Telnet and see what sort of answer I got. If there's not any access to terminal/SSH, I suppose you might try some variation of the -D or -d flags in the "additional parameters" section of your mail() call (param #5) ... I've never played with that, though, so YMMV.