Para ser preciso: não há diferença real, pois ambos são inseguros. Existem vírus que infectam o MBR, que é uma área que não é tocada pela formatação, seja ela rápida ou completa. Enquanto o Windows 95 basicamente matou esse tipo de vírus, fazendo algumas verificações simples para eles, executando em modo protegido e, em geral, impedindo que programas gravassem diretamente no disco, eles fizeram um retorno. Algum tempo atrás, houve uma execução de um rootkit que infectou o MBR no Windows. Se você tem isso, então você tem que iniciar em um ambiente limpo, ou seja, começar a partir de um CD ao vivo ou anexar o disco rígido para outro computador e limpe o MBR antes de formatar as partições. Sobrescrever a unidade (unidade inteira, não partições individuais) é outra maneira de realizar o mesmo.
PS! "Formato completo" significa hoje em dia "verificar o disco quanto a inconsistências" e não "limpá-lo completamente". De forma alguma impede que alguém recupere os arquivos, ele simplesmente garante que todas as áreas da unidade sejam legíveis. É simplesmente como as unidades funcionam agora.