I've had this. I got it as an add on for a plug in that I installed with MS Messenger. It was awful to remove, and I literally couldn't do it myself. And I'm pretty technical...
My solution came from an amazing forum called:
http://forums.spywareinfo.com/
You download and run a program called Hijack This, which provides a summary of everything currently running on your computer. You post your log to the forum, and a volunteer comes along and give you personalized, step by step instructions on how to remove it. Amazing place, and it shows how many volunteers there are you there willing to help out.
I'm not sure Sticks needs to do a reformat yet, although, it's sure to fix any problem with Windows. And make it run way faster as well. I just did a reformat on my computer... very refreshing.