I have this issue with a user who uses AOL to email me, I do not have this issue with any other person. When they email us they get the following rejection email:
Deferred: Connection timed out with mail.xxx.com.
Message could not be delivered for 3 hours
Message will be deleted from queue
The exchange server was never offline for 3 hours