It would be helpful if you filled us in on exactly how the beast is behaving. Absent any other clues, I'm guessing you have a Vundo variant; they're insane to try to get rid of, and yes, wiping the hard drive is a valid option.
AVG and Avast can't help you now. Time to reach for harder stuff such as killbox, hijackthis, and there's another ... can't quite remember the name offhand ... I'll post as soon as it comes to me.
If the PC contains critical data and wiping it would suck, there are alternatives, but they aren't easy.
-edit-
Not what I was thinking of, but have you tried Windows Defender? Very well-reviewed, and free.
Bookmarks