It is preferable to schedule a boot-time scan in Safe Mode - rather than run the scan in Safe Mode.
The thing about a boot-time scan is that the scan clicks in before the programs start loading. But nevertheless, not that big a deal as your system repair is at point that you now are, and that is what you have to deal with. If you can still boot into Safe Mode, your system is not yet ruined. It takes a bit of work for a user to ruin their system. In some regards you have to know how to ruin a system before you can actual do it. But obviously a malware infection can do it for you.
From what I gather, you have not tried a rescue CD yet.
