Yep, i too have experienced this problem (grr microsoft)..

They do have a KB atricle for this: http://support.microsoft.com/kb/829361

Cause:

This issue may occur when the following conditions are true:

  • The Microsoft Active Directory directory service closes before Exchange 2003 services are fully stopped during the computer shut down process.
  • Exchange 2003 is installed on a domain controller computer that is also a global catalog server.
  • No other domain controller or global catalog server is available in the forest.

Active Directory shuts down before Exchange 2003 services are fully stopped during the computer shut down process. When this issue occurs, the Exchange DSACCESS component may continue to try to contact the Active Directory and wait for a response.

Workaround:

To make a Windows Server 2003 domain controller computer that has Exchange 2003 installed shut down faster, manually stop the Exchange 2003 services before you shut down Windows.

OK, so i have just put together a small batch script to stop the services:

    net stop MSExchangeES
    net stop IMAP4Svc
    net stop POP3Svc
    net stop RESvc
    net stop MSExchangeSRS
    net stop MSExchangeMGMT
    net stop MSExchangeMTA
    net stop MSExchangeIS   /Y
    net stop MSExchangeSA   /Y

Run this batch script and then shutdown your server – check how fast it shuts down now!