Yeah, give it to me, baby!

Read the solution I found on http://www.huntug.org/DesktopDefault.aspx?tabid=94&frmView=ShowPost&PostID=13

*** cut here ***

KB 829361 recommends manually shutting down the Exchange services
before shutting down the server, which you can do with a batch
file. The following batch file shuts down the Exchange services
then initiates an immediate shutdown followed by a restart:

stopExchange.cmd
@Echo You’re about to stop all Exchange services and
restart this server. Press Ctrl-C to abort.
pause
net stop imap4svc
net stop pop3svc
net stop resvc
net stop msexchangeis
net stop msexchangemta
net stop msexchangesa
net stop msexchangesrs
net stop msexchangemgmt
shutdown /t 0 /r

I ordered the services to avoid a dependency prompt. You would not
include the MSExchangeSRS service unless the server were running
Site Replication Services in a mixed-mode organization. You may
need to add POP3svc and IMAPsvc if you use these features on your
Exchange server. You’d need admin rights on the server to run the
batch file, of course.

Following restart, you can run a similar batch file to start the
Exchange services:

restartExchange.cmd
net start resvc
net start msexchangemta
net start msexchangesa
net start msexchangeis
net start msexchangesrs

If one of services is already running, that line item in the batch
file will simply error out and the batch file will proceed to the
next service.

To automate the restart verification, run the batch file as a
Startup script in a Group Policy Object linked to the Domain
Controllers OU. Target the GPO to members of the Exchange Domain
Servers group to avoid getting start-up errors on your other
domain controllers.
–Bill Boswell

*** cut here ***

Thanks, both Bill Gates and Bill Boswell!

Exchange Server 2003 Computer Takes Longer Than You Expect to Shut Down