Outbound messages are being delayed randomly. You can send them to the same host—sometimes they don't queue up long enough to even see. Other times they are there for hours. Also inbound Internet mail randomly will time out with a "unable to find host" error.
Can you explain this?
There are a lot of variables involved here, but I'd take a close look at your connection. If you're connecting through a Proxy server, check the error logs on the proxy and make sure you have the latest service packs installed. If you haven't reset it in a while, that might be worth a try as well.
I'd also check your bandwidth utilization to make sure that something isn't filling your pipe and causing other things (like e-mail) to stack up.
I assume you've already checked the Event Viewer on the Exchange server for clues and spoken with your ISP to make sure they haven't been swapping out their routers for the last few weeks?