PhotoRec foi criado exatamente para esse problema. "Foto" no nome vem por razões históricas, mas o programa agora lida com centenas de tipos de arquivos.
O PhotoRec é uma ferramenta gratuita e original usada para salvar arquivos JPEG do cartão SD da câmera, onde as informações do diretório foi perdido.
Foi mencionado no episódio 150 do podcast de rádio RunAs. URL de download de MP3 (24 MB, 43 min 32 segs). Eu vou ver se consigo encontrar o lugar exato onde foi descrito.