Are you saying the webserver is having trouble sending the mail to the mail server to relay, or the mail server itself is having trouble sending the messages to the external recipients?
I would check the usual suspects:
- proper, valid, non-dynamic-looking (host1-23-34-45.host.com) reverse DNS
- corresponding forward dns
- HELO name matching reverse DNS
90% of the time one of those things is the problem. I wouldn't worry about SPF, it's more of a way of telling who isn't legit rather than who is legit.