well vinny, this is not a told you so, but do you now see why we keep advocating the use of Firefox or Opera in the other tread. This thing most likely installed itself through the ActiveX functionality of Internet Explorer then gain direct access to any and all your system due to the fact IE has basically "root" priveledges in the windows system.
Now onto the removal. The first thing you do is: window key+pause, when the system properties opens select system restore and disable it. From the sound of it its using it to reinstall itself each time it gets removed.
No try the removal procedure again. Afterwards go here:
http://www.kaspersky.com/ ----- probably the ebst at scanning archives
and here:
http://www.bitdefender.com/ ----- very good heuristics
And run their free online scans. The last one in particular will be useful since it will attempt to remove stuff too not just report it. If you keep getting strage errors it means the piece of malware is blocking access to security sites and we'll have to edit your hosts file.
You might also give a try to the trial version of Nod32 its an excellent antivir app. Just make sure you don't run two antivir apps in the same time.
monster avast its ok if you are on a budget but I've seen it fail numerous times personally to know its quality is so-so. Oh and downloading codecs is not different from downloading any of the other stuff on the internet. What it matters is where you get it from.