Do you have an old DOS boot floppy? Left over, perhaps, from the old days?
If you can boot from that, then you can almost certainly delete the files with no problem.
Otherwise, borrow or burn a Linux bootable CD - Knoppix or Mepis would allow you to inspect the hard drive, and potentially to delete files on there.
I'm surprised that Safe Mode wouldn't let you do it - it does indeed sound like a virus.