What are the incoming and outgoing email settings?

Make sure that both your incoming and outgoing email server settings are set to the following:

mail.yourdomain.com

Check to make sure your email client (typically outlook or outlook express) has outgoing email set to use authentication.

Your ISP may be filtering PORT 25. More and more ISP's are following in this trend that prevents any email other than yourisp.com from being sent from your ISP. Typically contacting them (your ISP) will get this resolved. 

Another option is to set your outgoing mail to use PORT 26.

Example: Outlook Express:
1) Click on "Tools".
2) Click on "Accounts".
3) Select the email account in question.
4) Click the "Properties" button.
5) Click on the "Advanced" tab.
6) Next to "Outgoing mail (SMTP):" Type in 26.
7) Click the "Apply" button.
8) Click the "Ok" button.