503 error - emails bounce from some recipient servers

I dont know why but every emails bounce from some recipient servers, like for hotmail, aol, and some other business servers. The error message is written below:

The following recipient(s) could not be reached:

someone@hotmail.co.uk on 05/12/2007 20:13
There was a SMTP communication problem with the recipient's email server. Please contact your system administrator.
<[mydomain].co.uk #5.5.0 smtp;503 This mail server requires authentication when attempting to send to a non-local e-mail address. Please check your mail client settings or contact your administrator to verify that the domain or address is defined for this server.>

The domain that we are using is hosted by an ISP, but our outgoing email server is a local box running SBS 2003. Most of the emails to most servers work well. DNS/MX reports are alright for out domain and every clients are on Windows XP using Outlook 2003.

In Exchange 2000 and Exchange 2003, the Simple Mail Transfer Protocol (SMTP) connector replaces the Internet Mail Service in earlier versions of Exchange for mixed mode environments. However, it should be noted that in pure Exchange 200x environments, a connector is not a requirement for Internet mail flow. This article explains how to configure the SMTP connector. More information can be found here - http://support.microsoft.com/kb/265293

There is an article that describes the most common setups that you can use to set up Windows Small Business Server (Windows SBS) 2003 for Internet access by using one or two network adapters. You can follow the article over here - http://support.microsoft.com/?id=825763