Eu usei bastante o Photorec e, embora seja um acerto ou um erro, às vezes ele sempre parece se recuperar mais do que eu imaginava. Eu não posso falar sobre como isso funciona internamente, embora seu site diga que você pode baixar a fonte lá.
Quando você apaga um arquivo, o sistema operacional geralmente não elimina os dados. Em vez disso, ele remove os metadados do arquivo (dados sobre o arquivo) da tabela de arquivos nessa partição. É o equivalente a arrancar uma página de uma lista telefônica: as pessoas ainda estão lá, mas não podemos chamá-las porque não sabemos o nome delas, o número ou o local onde elas moram. É por isso que os nomes de arquivos que ele recupera não são os nomes originais.
Sem um cabeçalho, ele tenta verificar a unidade em busca de identificadores de determinados tipos de arquivo. Por exemplo, arquivos do Word, JPEGs, etc, todos têm um certo padrão de dados no arquivo que o identifica como tal. Photorec vê isso e percebe que é esse tipo de arquivo.
Experimente e veja o que é recuperado. Espere deixá-lo funcionar por muitas horas, dependendo do tamanho da sua unidade. E, claro, certifique-se de recuperar para uma unidade diferente da que os arquivos foram excluídos de . Caso contrário, você irá sobrepor os dados que você está tentando recuperar.