anti virus - Clean up infected computer from viruses

I have a computer which had AVG Free installed from day one.
After several months of operation, it starts detecting viruses and trojans all the time.

Besides running a full scan, what should I do to clean the computer? Should I install another anti-virus or anti-malware tool (can it help?), or once viruses infect a system the only real solution is a clean format?

(Lately I've heard of viruses that burn themselves in the BIOS, so a clean format might not always work ... how common is this technique? Should I burn a fresh BIOS as well?)

Answer

once viruses infect a system the only
real solution is a clean format

This. Once your system is infected, you cannot trust any program it's running not to be interfered with by the virus - including all antivirus software. Theoretically, you could boot an antivirus system from CD, but even then, you can't be sure that the virus hasn't hidden a copy of itself deep in some executable from where it can reinfect the system.

Lately I've heard of viruses that burn
themselves in the BIOS, so a clean
format might not always work ... how
common is this technique? Should I
burn a fresh BIOS as well?

Pointless, since you'd be doing so while a hypothetical BIOS-resident virus is running. The only way to be certain would be to remove the BIOS flash chip and rewrite it using dedicated flashing hardware.

But I think BIOS-resident viruses have so far occurred only as proof-of-concept implementations and not been spotted "in the wild". It sounds nasty but is not actually very attractive to virus writers, since it would have to deal with (at least) dozens of different motherboard families, each with its own proprietary BIOS flashing protocol.