You may check your event viewer for any errors. see if any particular application is causing the slow shutdown.
Here are a few registry tweaks to speed matters up:
Auto End Task
This registry setting ends the running task and automatically shutdown the application
Go to Start > Run, type regedit to open Registry Editor.
Navigate to HKEY_CURRENT_USER\Control Panel\Desktop
Scroll down to find the registry key called AutoEndTasks. Right-click on the key, select Modify and change the value to 1.
Exit Windows Registry after making changes.
Wait To Kill Application
This registry key function is to set the time interval for Windows before killing the applications to shutdown the computer.
Navigate to: HKEY_CURRENT_USER\Control Panel\Desktop
Scroll down to look for the Registry Key called WaitToKillAppTimeout, right-click on it, select Modify and Change the value to 1000.
Hang Application Time
This registry key sets the hang time of the application before closing.
Navigate to: HKEY_CURRENT_USER\Control Panel\Desktop
Scroll down to look for the Registry Key named HangAppTimeout.
Right-click on it, select Modify and Change the value to 1000, exit Windows Registry
Clear Page File Before Shutdown
Last but not least, make sure Windows doesn't clear the pagefile on shutdown:
Navigate to: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\Memory Management
Scroll down for the Registry Key named ClearPageFileOnShutdown, if this is set to 1, right click on it, select Modify and Change the value to 0.
Wait To Kill Service Timeout
This registry key sets the time for Windows to wait before ending services related to Microsoft.
Navigate to: HKEY_CURRENT_USER\Control Panel\Desktop
Look for the Registry Key named as WaitToKillServiceTimeout, right click on it, select Modify and Change the value to 1000.
Source
p.s.: if you're looking for the easy way out, grab Superfast Shutdown, it does what it says on the tin, guaranteed :)
Best Answer
I ran Sysinternals ProcMon once to see what a machine was doing that took it so long to think about shutting down. The answer: explorer.exe scanning the Recycle Bin. So in this case I was able to speed up the shutdown of this machine hugely, by simply emptying the Recycle Bin.
It also explains the reason why it's quick the second time round: because the relevant part of the file system has been cached.