I had a similar problem with my SMTP connector on Exchange 2003. At first, my SMTP relay was a Server 2000 box running Symantec Security for SMTP Gateways and I just recently replaced that with a Barracuda box as the new SMTP Relay (incoming and outgoing). It used to happen a lot at first but then it just sort of cleared itself up (Knock on wood, lol). I remember that I got the mail to dump out of the queue after restarting the SMTP service on Exchange. I also remember turning on some diagnostic logging and found no real anomalies also. I know that probably isn't very helpful but just wanted to share! :-) PS Any big messages that were waiting to go out?? I actually set up a delay for messages for 20Mb to be sent out after normal business hours and I found that helped my issue of the queue's backing up as well.