My Vista install takes absolutely forever to reboot. So I only reboot when I have critical system updates that are being enforced by IT (I'd run it naked as well, but IT again enforces restrictions on that). Seems to avoid the problem satisfactorily, if not ideal.
I just timed a typical reboot on my Vista machine and it took 9 minutes (plus some change). Enough time to go to the Starbucks on the corner and return with a foamed latte.