You didn't mention what internet security/firewall you have in place. If you don't have something, consider purchasing Norton Internet Security. I have the 2003 version and have not had any problems (at least that I have traced back to NIS). About 6 mo. ago, there was some chat from people dissatisified with NIS 2004, so I bought a copy of Norton Systemworks 2003 (which included NIS) off Amazon for next to nothing. I don't know current availability.

Alternatively, activate the firewall in Windows or download similar freeware (e.g. ZoneAlarm).

As to reinstalling Windows, until you are sure that you have stopped whatever was planting the adware on your computer, you may just infect any newly installed programs. However, if you are running a version of Windows older than XP, it is probably worth considering upgrading to XP, but make sure you have everything backed up before starting the process. The firewall in XP may be stronger than that in prior versions, so it may help your situation.