Mmm, I was thinking about the registry entries idea, and it may not work, there may be other problems at hand because I've never seen this happen before. It sounds like you got some spyware that attached itself to the firewall or something.

If it's easy enough to do, I would personally format and reinstall. Many benefits from doing that and it'll fix your problem at the same time.