If you want to continue to use windows, I have a simple solution located on our server at work:
http://www.i2g.net/hijack.exe - This basically looks at the registry strings and finds what has changed and allows you to check them and get rid of them, it does the job!