This can be a loaded question. There are a few free anti virus solutions that do a good job. Avast, FreeAVG, and Microsoft Security Essentials. There are also several that offer free online scans, Panda being one. I'd strongly suggest trying the free online scan from Panda, and then after that downloading and installing one of the other 3 programs.
And check with your internet provider. Many of them provide a subscription to McAfee or similar included as part of your monthly fee. So even if you did buy something, you may be able to return it and save your money.
RE reinstalling Windows. It really depends on what you have. There are a few different types of nasties, viruses and malware being the two biggies. Viruses can do more damage, but tend to be silent. They like to spread and cause mischief. Malware tends to be more of an annoyance, and causes all sorts of popups, loads rogue programs, that type of thing. Viruses tend to attach themselves to your actual files. So they build themselves into your word docs, screen savers, etc. Malware attaches all sorts of things to Windows, but usually runs as a standalone file. So if you do have a virus, reinstalling Windows probably won't resolve it. Your actual files would still be infected, and would need to be cleaned. You may need to fully format your hard drive (losing all your data) and start over from scratch. Malware on the other hand, can often be fixed by reinstalling Windows. This removes the "hooks" the program has into Windows, and then doesn't get run. The files are still on your computer, but Windows won't load them.
I would also suggest downloading and installing Malware Bytes and SuperAntiSpyware (both have free versions) to see what they find. Most anti virus programs still tend to focus on just finding viruses, while anti malware programs tend to focus on just finding malware.
There are a whole host of things that may need to be done to fix it. Booting into safe mode, building a recovery/cleaning disk, etc, but start with doing some more AV scans and also a malware scan.
I've worked in the IT industry my whole life and get some strange satisfaction out of seeking out and destroying those little buggers. Some can be very tough to clean out. If you get data from either the AV or malware scan indicating what you have, try checking the forums at bleepingcomputer to see how to best clean them.
