Something is fishy. I've never heard of system restore not solving such an issue before. I'm sure you've done the Google thing and found pages like this
http://www.iamnotageek.com/a/342-p1.php
You may want to check and see what applications you're running. The terms for some shareware applications is that you install crap like this and they'll do it every time you load them.