Sounds like the only options then are to use a bootable antivirus disc (Kaspersky Rescue Disk is my fav and the one I use) or to wipe them (reformat) and start over (reinstall Windows OS).
Some stores don't know about the bootable AV's (pretty new technology in hardcore virus removal), and just say to wipe it. If you don't have data backups, let me know before they do that and I can send you instructions on how to try the Kaspersky disk.