There are a number of trojans and spyware programs that can cause exactly what you are describing.
Not all security software will notice these either. My roomie's laptop, for example, had all the latest McAffee Antivirus and Internet security software and did scans weekly but totally overlooked these trojans.
AVG can find them, as can Lavasoft's AdAware Pro.. both freely downloadable. I'd recommend starting by installing these and running them.
If you're a bit more Windows savvy, you can also rather quickly check yourself with regedit and doing a find on "explorer.exe" and looking at all the bazillion keys with %SystemRoot%\explorer.exe (params). You'll have to manually click on these as the trojans I've found that hook on to this add like a TON of spaces to the end, then the trojan.. such as:
SomeKey="%SystemRoot%\Explorer.exe /iidit %i %k
(like 500+ spaces later) minstall.exe"
Which basically launches an explorer.exe process with a trojan attached, which can error on exit. In regedit, due to the spaces, just looking at the key wont show as it's scrolled way past the right margine of the viewer.
Sneaky bastages...