A few weeks ago we switched one of our clients to use a hosted anti-SPAM/anti-virus solution. Everything was fine before that, but ever since we did so I started getting delays in the initial welcome message the mail server gave. I thought (And that’s where I went wrong) that it might have been caused by the provider, sending the messages in bursts.
Yesterday I got sick of all the warning messages I got from the monitoring server and decided to do something about it. The customer care people pointed me to a page waaaaaaaaaaaaaaaay deep inside their interface to see how much traffic is passing, only to see that the server is getting much less traffic than it can handle.
Anyways, a short session of troubleshooting leaded me to the cause. So my advice to you, troubleshoot, never think.