Erasing everything is the best option once you've backed it all up though

Anyway, I'd suggest running your spyware/adware scanners in Safe Mode after you've updated them (don't try updating them in Safe Mode), since otherwise it's easy for them to block you cleaning them up Use Spybot S&D as well as Adaware. You might want to run a HijackThis scan after you've cleaned up and booted back to normal mode, and post the results so we can see if it's really clean or not