This is why it is much harder to remove a virus than to block it in the first place. Sometimes booting to safe mode is sufficient to prevent the malware from starting, making it easier to detect and clean. Other times it is not so easy.
There is a class of malware called a master boot record or boot sector virus. This malware starts before the operating system. Boot sector viruses are removable, but generally speaking they are the hardest to detect and hardest to remove.
One way to remove it is to just rewrite the boot sector with known good standard boot code. This may work to eliminate the virus, but it might break other features, such as the ability to boot in to a diagnostic or recovery partition.
If this doesn't work, it may be ultimately necessary to erase the entire hard drive, low level format, recreate the partitions, and reload everything from scratch. This is a long, involved process that is usually not possible for most computer owners to do, because computer manufacturers no longer supply an actual Windows installation disk. Fortunately it is rare to have to go quite that far.
Most computers now only come with a 'Factory Recovery' solution. Typically this is on a hidden partition of the hard drive, and you get the computer to boot to it by pressing a certain key combination when the computer is first starting up.
You can usually also create a set of self-booting factory recovery disks from within Windows, so if you can't boot from the hard drive at all you can still run the factory recovery program.
A factory recovery may work, but not always.
The first problem is most users fail to make the factory recovery disks when they first set up the computer. If the hard drive physically fails, or if the recovery partition is corrupted for any reason, there's no way to get to the recovery data.
The second problem is that even if the recovery disks are available, they may only restore the user partition, not the entire hard drive. They don't do a low-level format or overwrite the entire hard drive, so they may not eliminate a boot sector virus.
If the factory recovery disks are not available, then it may be possible to run the factory recovery program by pressing a certain key combination during the boot sequence.
However, if the boot code is damaged, it may not be possible to boot to the factory recovery partition. This is pretty typical with a major malware infection or Windows crash. I frequently encounter this problem. There are some work-arounds. Many times I can still access the factory recovery data and get the system partition restored.
There is another problem. Even if the on-board factory recovery program does run, it may not eliminate the boot sector virus. This is because the computer is still booting from the hard drive to run the factory recovery, and therefore the virus code in the boot sector is executed before anything else. It can hide itself in memory and then re-infect the hard drive even after a complete factory restore.
I've found that the Windows "repair your computer" program that can be run at startup or from a Windows 7 Repair Disk will generally not detect and fix the problem. There are some advanced command line tools as well as other programs and utilities and self-booting malware scanners that will clean up this malware, but it's not always an easy task.
Note: Pete Newell has provided professional computer services for 35 years. He can be reached at (315) 376-8879 or through solutions.prnewell.com.