Ok clean out any temporary files temporary internet and your temp file folder which you can access from the run prompt by typing %temp%.
Disable system restore as nastys can hide in there right click my computer properties system retore take the tick out of use system restore. Note that this will erase all your system restore points and do not forget to switch back on after you have got rid of the problem.
Make sure all of the above programs are updated and then run a full scan again in safe mode I would also add a2 to the list click here and adware click here and also run a full scan with your anti virus app.
If the problem is still there after this then download hijack this from click here and post the logfile to click here and they will help sort you out