I had a malicious spyware too. I tried everything as well. Made me reinstall my windows.
* SikStyles thanks Adeptus here for all the help again.
Anyway Adeptus also pointed me to
www.symantec.com on which I could find instructions on how to remove it. Sadly it did not work. Now if you could remember what it was go search on it and see if it says anything.