Have you always had this problem?
What ISP are you on?
Because some ISPs, such as FreeServe don't like you using any other outgoing mail server (SMTP) other than theirs.
If so... Then just use their smtp mail server (won't affect your email, or "from" headers, etc".
so for freeserve, use "smtp.freeserve.com"
Thats all I can think of for the minute.