Should be easy enough to remove without having to do a reformat. Boot your computer in safe mode, run all of your scanners and delete anything that comes up as malicious. Then dig through your registry for the program(s). It will have most likely made an entry there, which is why it keeps reinstalling itself.
Boom. Problem solved. If you need any tips on how to do any of the above steps, I'd higly reccomend using the all-powerful might of a few good search enigines. Scanners I highly reccomend are "Spybot Search & Destroy" and "Ad-Aware SE". Good stuff right there, and both free. That combined with a retail Virus scanner (or even AVG Anti-Virus, also free) can protect you fairly well.
I'd reccommend that if you do wipe your hard drive again any time soon (or if you haven't reinstalled the OS yet), that you should partition it so that you can have one section for Windows and only Windows (or whatever OS you run) and the other section(s) for the rest of your general junk. I've got my HDD's partitioned into a grand total of 7 drives... Just in case
EDIT
Yeah... Um, the exploit patch works too I suppose...

Thank you, koneko.