Not able to send emails outside of network

have an Exchange 5.5 SP3 server servicing 60 Outlook 2000 clients. About half the clients keep getting the following error when sending email to reciepients outside the company:

No transport provider was available for delivery to this recipient


Everyone here is using Outlook 2000. We are using Exchange 5.5 for internal
emails which work fine. If I remove the exchange service off the client I
can then send emails outside from those users that were having the problem.

Now it doesn't happen to everyone and we can all receive emails from outside
the company. I have checked the settings on the users that are having
problems and they are all correct.

I tried moving the exchange services in the delivery tab to the top of the list and that did not work either.

Any help is greatly appreciated

Greg