adrianTNT - 5:28 pm on Feb 2, 2009 (gmt 0)

You may want to try additional or different DNS servers that your mail server uses. I seem to remember that we had a flood of mail problems some months back that was got fixed by changing the DNS entries.

I recommend this too, I had this issues few times with my dedicated servers. I cannot remember the file name to be edited, there is a file that contains the DNS names (usually 2 lines), and the DNS mentioned there ware offline, that caused the email connection to fail and emails got stuck in queue.