Is your computer behind a router or hardware firewall?
If not, you should download a firewall like ZoneAlarm and burn it to a CD. Then disconnect your computer from the modem before reformatting and reinstalling. Before going online install the firewall to prevent any viruses taking over your computer.
I posted a thread about doing a clean install of WindowsXP a little while ago. Most of it should also work for WindowsME. Basically the link I posted talked about downloading all of the patches for the operating system and burning them to a CD with a few other programs. This would give you a fully patched system before you even hooked up to the internet.
A friend of mine had his computer taken over within minutes of a clean install by the Blaster virus. It does kind of ruin your day.
goates