The Message Transfer Agent (MTA) doesn't always do what you expect. Here are two examples of MTA problems I've seen recently.
The first problem occurs when you delete a mailbox or custom recipient from the Directory and the MTA generates nondelivery reports (NDRs) for messages sent to a distribution list (DL) that formerly included the deleted object. The Microsoft article "XCON: NDR Returned for Deleted Mailbox When Message Sent to DL" (http://www.support.microsoft.com/support/kb/ articles/q194/5/04.asp) describes the most likely explanation of the problem in Exchange Server 5.0 and 5.5. To increase performance, the MTA maintains a cache of directory information. When the MTA needs directory information, it looks in the cache first, then in the Directory. However, when the Directory doesn't update the when changed attribute on a DL when someone removes an object, the MTA doesn't know to refresh its cache. Exchange continues to generate NDRs on messages sent to the DL until you stop and restart the MTA service. Microsoft's fix (which is in Service Pack 2—SP2) forces Exchange to refresh DLs in the cache every 10 minutes.
Another problem is that a message can get stuck in the MTA queue while other messages flow around it. The cause of this problem is a subtle loss of synchronization when a sending server transmits a message before the receiving server is ready to accept it. Eventually, the message times out, but while the message is stuck, other messages flow normally. You usually see the problem only in hub servers that handle a large volume of messages and connect to other bridgehead servers across fast network links, but it can also occur between two servers in the same site. The Microsoft article "XCON: Message Sticks in MTA Queue While Other Messages Flow By" (http://www.support.microsoft.com/support/kb/articles/q194/7/50.asp) describes the problem in detail. An administrator viewing the MTA queues sees that the timed-out message is stuck, and the only solution is to stop and restart the MTA. This action seems excessive because the other messages are working. The condition is rare, and Microsoft has fixed this bug, too, in SP2.