1) Cover the square hole in the corner of the floppy with a piece of tape (there should be two holes - you want to cover the one WITHOUT the write-protect shutter). If you hold the disk parallel to the floor, with the label side up and the metal shutter away from you, it will be the hole on the right.
2) Use the DOS command "FORMAT A: /T:80 /N:9"
Windows XP doesn't even support the /F:720 switch anymore, but explicitly defining the number of sectors and tracks works just fine. It sounds like you're using Windows 98 or ME, so the /F:720 switch should still be supported.
I just tried these steps again on an XP machine to make sure they worked. Covering the second hole and using the /T and /N switches worked fine. When I tried it without taping over the hole, I got the "Invalid Media or Track 0 bad disk unusable" error, so I'm pretty sure taping up the second hole is the key step.
go to www.exefind.com/format-floppy-disk/ shareware works on xp sp3 as well as xp sp2. had a slug of 720 disc, used max format program, they cleaned up fine.
Getting old labels off was more of a paine then re-formating 720 kb.