.. if I had a machine that had been that seriously compromised I would want to do a format and re-install.
I wouldn't. I'd want to find out HOW this happened first before doing a format/re-install. Otherwise the hole still exists. And wiping may not be a solution if sensitive data is on there (and no backup or recent backup has been made). A definate task after whatever has been dealt with (access retrieved) would be to determine how this happened and prevented it from happening again (appropriate patches, upgrades, disabling floppy/CDRom, locking USB, restricting access to server/server room, etc.)

It is wise, however, to get permission to do this activity in writing from the boss (this would be a CYA).