I'd say it sounds more like you've got a massive spyware infestation, possibly even a virus or worm. It also sounds like the damage has progressed to a point where the best option would be to format and start over.

Back up anything you don't want to lose, and then stick in the recovery disc that came with the system. Let it do it's thing, then you can start putting those files back.

This time make sure you have a virus scanner and that it's constantly updated, and download a couple of spyware removal tools and update/run all of them freequently (at least once a week).