Mail messages are stuck in my outbox with SQL Mail.

A. This is a mapi problem, not a SQL one - specifically with the mapi32.dll file. The one that comes with NT 4.0 as part of basic "Windows Messaging" does not work properly when called from a service. 

Versions of mapi32.dll that people have reported to work are :-


The one in NT 4.0 SP3 (mapi32.dll doesn't ship in later sp's, so it has to be SP3)
Outlook 97/98 or a recent Exchange client
v5.5.1960.0 (size 884736 bytes)
Outlook 2000 definitely fixes the problem (I did this on a server recently).

Another cause of the problem can be having offline folders enabled on the mail client. Make sure this isn't the case.