Não entendi essa do primeiro técnico de "abrir uma nova partição". Ele criou uma nova partição sobre a antiga?
Vou tentar explicar melhor como tudo acontece. Quando você apaga algo, seja deletando o arquivo diretamente ou apagando a partição inteira os arquivos continuam no disco, só que agora eles não podem mais ser acessados da forma convencional e aos poucos vão sendo sobrescritos (os novos arquivos criados ou modificados "cobrem" os arquivos deletados). É como se você pegasse uma folha de papel que já foi usada e voltasse a escrever nela. Conforme você fosse escrevendo, o texto que já estava no papel iria desaparecendo, dando lugar ao novo texto escrito.
Sendo assim, dependo do que o primeiro técnico fez, os arquivos já podem ter sido sobrescritos, por isso a segunda empresa disse que não poderia salvá-los, já que estes arquivos não existem mais. Os arquivos corrompidos são aqueles que foram sobrescritos parcialmente. Você consegue encontrar fragmentos deles, as partes que sobraram, porém não consegue mais acessá-los por eles não estarem completos. De uma forma ou de outra estes arquivos também estão perdidos. Por isso a desistência da segunda empresa.
Quanto menos se mexe com um disco que perdeu dados, maiores são as chances de recuperá-los.