Did you turn system restore off before you tried to clean everything? Sometimes you have to do that to ensure everything can be removed.
Here's a link with a whole drawn out process. I've never tried it, and it sounds like it may take awhile, but I suppose it would be better than reformatting.
http://www.able2know.com/forums/view...110&highlight=