Now, Microsoft has a fix for SBS 2003 (with SP1 installed) which can be freely obtained by calling you local Microsoft PSS team. The fix links Active Directory and Exchange services and makes the directory service wait for Exchange to shutdown before shutting down itself.
For more information:
http://support.microsoft.com/default.aspx?scid=kb;en-us;887539
If you still need my workaround:
http://www.msexchange.org/tutorials/Accelerating_Exchange_Shut_Down.html