If you don't want to reformat it and really just want to get rid of the viruses, it'll take a bit of work since it sounds like theres alot of crazy stuff on that computer (i've seen much much crazier though).
First off, you should try using more than one program.
When I know I have a virus, or someone asks me to get rid of a virus, I use several different free virus cleaning programs; Spybot S&D, Avira Antivirus, AVG, and last time my brother's computer had a virus I also used Malwarebyte's Anti-Malware. I also use something called HijackThis, but I wouldnt recommend using that unless you know what you're doing.
So....go to download.com and try using at least one other virus cleaning thing.
After you're done using em, uninstall em.