Using Vista Ultimate I usually get a shutdown in 10-15 seconds. One thing I do now is shutdown all running programs before starting the procedure... I feel this makes for faster shutdown but I also get satisfactory shutdowns without this.
I had the same issues you are experiencing with Vista Home Premium... that OS was never satisfactory on a new HP system purchased in early 2007. Never solved it and tried Vista Ultimate... difference in night and day and never looked back.
Hope this helps... you might try shutting down all running programs to see if it helps.
It seems Vista on my laptop boots in short order, though longer than a XP system. However, during shutdown seems to drag on. The real nagging point for me is the relative "constant desktop display" practically showing no activity until the actual power down. The HD led is at work, but to wait 4min. or more is that "normal"? Other Vista systems take as long or shorter, it varies I just wonder what a typical shutdown time is? I can't get a straight answer and, it seems gotten slower after the SP1 update. Comments -----Willy