So, you say that when ever you start the computer up, even after doing a full system restore (the one that removes all your data) the restart issue still occurs?
If so, it is almost 100% likely its a hardware issue (any part of the computer, really)
If not, I forgot to mention this:
Follow the directions to get into Safemode again, but instead of selecting Safemode, select "Last known good configuration" (I am not 100% positive that option is avaliable in Windows ME)
It should be like System Restore, and will just automatically choose a restore date, without loading any drivers.