Might be nothing to do with the problems you are having, but worth bearing in mind. I have seen problems with emails not getting through due to a line length limit. Some servers adhere to standards which define a maximum length of 998 characters and will not accept the incoming email.

Welsh longbow :)