Blank im going to go along with a few people, a format and install will definately be the best bet. Whatever you do, if you can avoid it, do not put ME back onto that PC. 98 Second Edition is much better if you want a 9X series OS. Otherwise 2K is another great idea.
If you think it can run it, then XP is always good aswell.
Im sure their has to be somewhere you can get yourself a copy of one of these OS's. Surely. Even if you could find a ME cd, and ring up the dude you bought it off to give you the serial number, then it would still be legal.
Format+Reinstall=Good.