This happens with Exchange 2003/2000, because Active Directory services shuts down before Exchange services shut down. It happens more often on Exchange 2003 because service shutdown in Windows 2003 has been accelerated.
Shutdown Exchange services by using a batch command, before you shutdown the server.
net stop “Microsoft Exchange System Attendant” /y
Stop “WinHTTP Web Proxy Auto-Discovery Service” service manually, before you shutdown the server.
net stop “WinHTTP Web Proxy Auto-Discovery Service” /y
Decrease the value of “WaitToKillServiceTimeout” in the registry:
The default value of “WaitToKillServiceTimeout” are: 600000 and should be changed to lower number.
This value should be found by experiments and may impact other services in the system and this change is not supported by Microsoft.
Note: You may need to install the latest Exchange 2003 Service Pack to reslove this issue.