Exchange 5.5-problem transferring email

I am running an Exchange 5.5 Server under NT 4.0. Both NT and Exchange are running under the latest Service Packs.

I am having an intermittent, but persistent problem where I am getting an error stating "Timeout occured whilst waiting for response from smtp server" when trying to upload or download e-mail over the internet. I have called the ISP and they state that the smtp server is on my side, not their side. The problem was occuring before I did the SP4 upgrade to Exchange.

Does anyone have any ideas?

Thank you.