Check your event logs for SMTP errors and post the exact errors. If you have not installed SP2 and all rollups and exchange updates install these as soon as possible. How long ago did the problem begin? What changes were made before the problem began?
One thing that occured to me after reading over the discussion… If you are running Exchange on Server 2003, make sure that you have all available microsoft updates installed. Last year I was having issues with people getting too many logins on the exchange server and was able to determine that there were issues with the scalable networking pack with server 2003 which was not compatible with some network cards and the fix was to disable the tcp chimney with the command Netsh int IP set chimney DISABLED. This is all explained in this article.
This problem was resolved with another Microsoft update which was released well after this problem was discovered which disabled this feature and is mentioned at the beginning of that article. Perhaps this may be causing your issue.