That sounds like some kind of trojan or virus type activity.
Which a/v package did you use, and was it the free/limited version or the full featured one?
Whatever it was is probably long gone now, since you started over. If you want to get a free second opinion, one that I use sometimes for that purpose is
http://housecall.trendmicro.com/ (free online virus scan)
Im dumping AVG this week, because the quality has been going south lately. I have been evaluating Kaspersky for the past 28 days - and love it. I'm also evaluating Avira AntiVir, but only on day 2. One of those 2 will get our business

(13 pc's in our building and home)
I suspect Kaspersky will be the choice, and the price is quite fair.
For 1 pc:
-$59.00/year for a single pc @ 12 months
For 3 pc's:
-$23.00/year per pc if you do 3 @ 12 months each ($69)
-$16.66/year per pc if you do 3 @ 24 months each ($99)
-$15.56/year per pc if you do 3 @ 36 months each ($140)
For 5 pc's:
-$20.00/year per pc if you do 5 @ 12 months each ($99)
-$15.00/year per pc if you do 5 @ 24 months each ($149)
-$13.26/year per pc if you do 5 @ 36 months each ($199)
For 10 pc's:
-$18.00/year per pc if you do 10 @ 12 months each ($179)
-$13.50/year per pc if you do 10 @ 24 months each ($269)
-$11.99/year per pc if you do 10 @ 36 months each ($359)
free 30 day trial is at
http://usa.kaspersky.com/trials/home-users/anti-virus-7/tp/
Mike
PS: If anyone reading this tries kaspersky, MAKE SURE you fully remove whatever program you have first - and reboot. You should never install two a/v programs at the same time, this can cause all kinds of problems. (exception being the trend micro free web scanner, which is safe to do with another program installed)