This is generally an authentication problem. To stop just anyone from using your mailserver to send spam, we require users to authenticate when they try to send email.

Check the outgoing server authentication by doing the following:

  1. Open the Account settings dialogue.
    In Outlook 2010 or 2013, it's on the File tab, in Outlook 2007 and prior it's in the Tools menu.

  2. Double click on the appropriate email account.

  3. Click  More Settings

  4. Choose the Outgoing server tab and check the authentication settings.

    You should have 
    My outgoing server (SMTP) requires authentication ticked
    and Use the same settings as my incoming mail server selected.

  5. Click OK to save the settings.