Turn off system restore
Boot to Safe Mode (press F8 during boot up)
Run Malware Bytes, Spybot and SaS, write down anything they find.
Try to use the above programs to remove the malware, but if the problem still occurs, tell us what problems they found.
There will probably be a specialist tool to remove whatever infection it is.
Bear in mind, that you probably have a very nasty rootkit infection, so the quickest and best option is almost certainly to re-install the OS. It honestly is often more hassle than it's worth trying to remove these types of infection.
If you use your machine for any kind of online banking, or online purchases, then I really wouldn't consider anything other than a fresh install of the OS.