Quanto mais você usar, menores as chances de recuperação. Quanto mais escrever no disco, pior. O ideal seria colocar seu HD em outra máquina, para utilizar outro sistema. Outro Linux ou até Windows. Pode ser um Liv CD também. Daí, então, utilizar uma ferramenta de recuperação, como o photorec (do pacote do testdisk). O testdisk em si é voltado para recuperação de partições.
Outras ferramentas:
http://foremost.sourceforge.nethttp://www.nucleustechnologies.com/Linux-Data-Recovery-Software.html (Windows)
http://www.stellarinfo.com/linux-data-recovery.htm (Windows)
No mais... Google it! Há mais ferramentas e até distribuições inteiras (Live) para recuperação de dados.
O grande problema é que muitas ferramentas, com o unrm, ficaram no tempo e não reconhecem EXT4.
A recuperação de arquivos FAT* e NTFS é mais simples. O sistema, em verdade, não apaga os arquivos, mas apenas seus índices. Já no EXT o serviço é mais completo: apaga mesmo. Daí complica a coisa...