Cannot send internal email to a external email host like hotmail, gmail, yahoo, gmx etc...

We have installed SBS 2003 with Exchange 2003 and we are pulling our email off from our isp's mail server with the microsoft pop connector. We are not able to send our internal email to external email like yahoo, hotmail, gmail, etc. I have searched for instructions from many articles but nothing is working for me. Below is the error that I am getting:

There was a SMTP communication problem with the recipient's email server.
Please contact your system administrator. <mycompany.com #5.5.0 smtp;550 relaying mail to gmx.com is not allowed>

There was a SMTP communication problem with the recipient's email server.
Please contact your system administrator. <mycompany.com #5.5.0 smtp;550 relaying mail to gmail.com is not allowed>

There was a SMTP communication problem with the recipient's email server.
Please contact your system administrator. <mycompany.com #5.5.0 smtp;550 relaying mail to hotmail.com is not allowed>

Any ideas how to fix this? Thanks

I think that since you dont have MX record and had been identified as a spammer. You may want to use a smarthost, usually your ISP to forward the email that you want to the outside world. You also have to ensure that the email address for the smarthost is enclosed in [].

Thanks for the information, but we are not using MX records. We are just pulling our email down from our email provider with the pop connector from microsoft. I am still working on this issue and let you know how it goes.