Not sure if this will work, but you could try it, Kaz.
Go to Start > Run, and then type in msconfig and hit Enter and the system configuration utility box comes up.
You should see several tabs across the top. One of them, when selected, has a box you can tick that says "Safe Boot". Tick that box, and then click Apply and OK and it will prompt you to restart the computer, which should then start in safe mode.
To change it back so that it boots into normal Windows, you have to go back into this same box to untick the "Safe Mode" box or it will continue to boot in Safe Mode.
However, there does seem to be an underlying problem as to why it won't boot into safe mode via the normal method, which hopefully someone will come up with an answer to. I just hope that the virus you had, or the removal of it, hasn't damaged Windows, in which case, you may have to consider a repair or re-installation of Windows.