What Tony said.

Also, try using a 3rd party mail server and see if that makes a difference (even better if it's on a server where you can access the mail logs.)