I had this same screwy deal.

Did a clean install from scratch on a Dell 8400. The loaded Vista upgrade. Loaded up my usual starting software, Norton Internet Security, MS Office Word, Excel, etc, Cable modem ethernet connection.
The machine worked OK, I thought. But when I did a normal shutdown, the machine stared up after just a few seconds, looked like a normal restart/reboot. This occurred both when shutting down fom the Start menu>> Shutdown, or when pushing the power button on the front of the machine. Unplugging trhe CPU yeilded the same results. On every restart, I got the black screen, with Start in Safe Mode, Start Normally, etc. I tried Start Windows Normally several times, and once tried Start Windows in Safe mode. Always started OK from there. But would continue withits restart antics.
I then performed a number of actions, including brushing and vacuuming all the dust on the inside of the cabinet, Cleaning the outside of the cabinet, and spraying a good dose of electronic spray cleaner to the start button, both from outside the switch and on the back of the switch, I dropped some unwanted startup programs with a Start Menu search for mscofig. Don't recall which one. I might have done some other things that I can't recall at the moment.
Now something fixed the deal. I have succesfully shutdowwn several times, without a single case of the errant restart. It could have been one/more than one/all of my actions that got 'er dun.

It could have been it fixed itself, or it could be a nasty the comes for a while, dissapears, then come back again. I don't konw.
But for those who have seen this oddity, hope is on the horizon. Just keep trying the possible fixes.