I have seen behaviors like this in the past with corrupt messages in the outbox. Once one gets in there anything behind it will fail to go out as well, so once they delete the offending message the rest tend to go out without further trouble. Is there anything special about the message they deleted that got things moving again? I'd be on the lookout for attachments, signatures or signature images, etc. If you can narrow that down it can make troubleshooting the issue significantly easier.
Kyle Kerst
Lead Internal Network/System Administrator
SmarterTools Inc.
smartertools.com