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.