once viruses infect a system the only real solution is a clean format
Isso. Uma vez que seu sistema esteja infectado, você não pode confiar em nenhum programa em execução para não ser interferido pelo vírus - incluindo todos os softwares antivírus. Teoricamente, você poderia inicializar um sistema antivírus a partir do CD, mas, mesmo assim, você não pode ter certeza de que o vírus não escondeu uma cópia de si mesmo em algum arquivo executável de onde possa reinfectar o sistema.
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?
Inútil, já que você estaria fazendo isso enquanto um vírus hipotético residente no BIOS estiver em execução. A única maneira de ter certeza seria remover o chip flash do BIOS e reescrevê-lo usando hardware flash dedicado.
Mas eu acho que os vírus residentes da BIOS até agora ocorreram apenas como implementações de prova de conceito e não foram vistos "em estado selvagem". Parece desagradável, mas na verdade não é muito atraente para os criadores de vírus, uma vez que teria que lidar com (pelo menos) dúzias de famílias de placas-mãe diferentes, cada uma com seu próprio protocolo flash de BIOS proprietário.