Eu perguntaria para o pessoal da empresa se eles de fato responderam em massa (o que talvez esteja até visível no e-mail, se não usaram "com cópia oculta" (talvez dê para saber se usaram isso também, ainda que você não veja para quem mais mandaram, ao menos sugere que o fizeram)), se poderia ter sido engano, ou o que. Enquanto isso, tascava mais umas escaneadas de outros antivírus, como AVG e o panda online.
Formatando o PC não tem como "sobrar" alguma coisa, se tem é novidade para mim. Acho que só poderia acontecer algo assim se o próprio programa que usasse para formatar estivesse "dominado" pelo vírus e não fizesse uma formatação completa, mas que fosse identificada como tal para quase todo o resto do mundo, e então, numa nova instalação, o vírus ainda estaria "lá", em algum lugar, necessariamente algum lugar estratégico em que fosse ser nocivo, em vez de simplesmente um arquivo "parado", largado no raiz.
Eu diria que, mesmo com windows, não tem como algo assim acontecer, a menos que fosse um windows pirata hackeado para vir infectado com vírus -- o que não sei se existe. Não me espantaria se existisse, mas nunca ouvi falar.