Exchange is famous for being the best application you can load onto a server to slow down shutdown.
This causes all kinds of problems in three situations:
1: Power failure, does your UPS have enough battery power to keep your server running while it shuts down.
2: Routine maintnennce... 'You wont be able to access your email for 5 mins betwe..... oh wait its exchange...'
3: You need to reboot it to do some work on it and get bored waiting for it.
To accelerate the shutdown the best choice is to manually shutdown the Exchange related services before trying to shutdown or reboot the server. You can do so manually by going to the Services snap-in in the Administrative Tools menu and stopping the specific Exchange related services, or doing so from the CMD:
Better yet you can create a batch file on the desktop to do it for you. Add the following likes to a batch file and run it beofr you shut down the exchange server.
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