Atualizar
De acordo com o documento vinculado por david, a recuperação de dados sobrescritos era possível com disquetes, mas quase impossível com discos rígidos modernos, então a idéia de recuperação é provavelmente melhor considerada um mito.
Estou deixando minha resposta original como representando o mito.
NOTA: O "mito" trata da recuperação de dados que foram sobrescritos fisicamente. Recuperar dados que foram simplesmente excluídos (não sobrescritos) é uma discussão completamente diferente.
Até onde eu sei:
Quando você sobrescreve dados no disco, os dados antigos são perdidos para as ferramentas normais do sistema. (Se não estivessem, uma leitura retornaria uma mistura dos bits pertencentes aos dados antigos e novos, para que seus dados ficassem corrompidos e você precisaria de um novo disco.)
Mas pode ser possível recuperar dados sobrescritos usando equipamentos especiais. O motivo é o modo como um bit é gravado em um prato magnético: Um "bit" é uma área magnetizada no disco. A área representando um único bit contém algumas centenas de "grãos" magnéticos, e a leitura de um bit retornará um 1 se um número suficiente desses grãos individuais tiver a orientação correta.
O truque é que a escrita nunca é 100% - a substituição pode alterar a orientação magnética de talvez 90% desses grãos, o que é suficiente para uma leitura confiável dos novos dados. Mas há algum magnetismo residual nos grãos que não mudou de orientação. Este resíduo pode ser lido se você tiver o equipamento adequado para isso, assim você poderá obter uma representação (um tanto barulhenta) dos dados antigos, sobrescritos. Combinado com a análise estatística, muitas vezes é possível reconstruir uma boa quantidade do material original.
Mas esse tipo de recuperação requer hardware especializado e, como Oli mencionou, é proibitivamente caro para a maioria das pessoas.