Sometimes you have to get down on your knees and do manual forensics work when one-hit wonders won't save you.
As a background, I, like most people, do not observe "least priviledged access" and other such best computing practices. Because people, in general, do not observe these practices, it is why we have a communicable-virus culture. While I do not observe best computing practices, I do have a level of smart computing practices that has apparently allowed me to go without any known-detrimental viruses through my whole history of computing, even when I do occasionally get a virus (and am always able to locate and expel it.) This is even in light of significant periods without anti-virus or a maintenance discovery strategy.
That said, I think it is not too much trouble to be able to realize you have a virus, ascertain how it works on a basic level, and rid yourself of it. You have many tools at your disposal that aren't even categorized under 'virus/spyware scanner'. For the things that always want to rename themselves, there is probably a process running that looks valid but is not, which runs the show, or otherwise DLLs or other system files are being hooked into otherwise legitimate EXEs. It's certainly annoying. You need a piece of software that allows you to track what files your executable uses/and accesses to realize if these issues are occuring.
It helps if you have a knowledge of what your computer SHOULD be running at any given time so that you can, with the aid of such a program, ignore any false-positives or -negatives (for softwares that flag 'strange things' hooking into your EXEs, for example.)
I will have to look up the name of a software I used most recently for this very reason. In the meanwhile, you want to use MSCONFIG to check for services added by unknown providers and that shouldn't be running, as well as stopping things from running on startup (also done through MSCONFIG and checking your Startup folder in shortcuts folder). If you do things like this and the processes/startup references come back, you'll know that there is a third party running the show, and that's when you have to do more investigative work.
----------------EDIT:--------------
I am having incredible trouble finding the software I use, bah
