Allora: sono finalmente riuscito a fare un po' di prove e posto i risultati, come riferimento per chi avesse in futuro lo stesso problema.

Photorec - recuperati 28Gb di files ma con nomi non originali in 1 sottolivello di cartelle di nome "recup_dir1", "recup_dir2" ecc.
Foremost - recuperati 14,2Gb di files sempre con nomi in codice in 1 sottolivello di cartelle di nome i vari tipi di files (avi, mpg, doc, pdf, ecc.);
Scalpel - Ho fatto due tentativi, poichè il primo mi dava un totale di 342Gb recuperati (la prtizione è da 129Gb!) quindi molti doppioni - il secondo mi ha dato 10,3Gb di files recuperati (!) sempre con nomi in codice e divisi per tipo di file in più cartelle (es: html-0; html-1; ecc.)
Infine ho provato anche il demo di Stellar Phoenix Linux che sia in modalità Quick Recoveri che Advanced Recovery mi ha dato gli stessi risultati: sui 6,23Gb di files recuperati in 1 livello di sottocartelle dal nome sempre in codice ma molti files avevano il nome originale, anche se in maggioranza con lunghezza 0 bytes e quindi di fatto non recuperabili; inoltre qualche sottocartella aveva il nome originale ma con contenuto nullo...
In conclusione, sembra che come recupero sia più indicato Photorec, anche se si perde il nome originale e alcuni file, nonostante abbiano un'estensione di un certo tipo di file, magari risultano corrotti ed in realtà sono un altro tipo (ho provato a cambiargli estensione e si aprivano in quest'ultimo formato... boh...).
Occorre quindi sputare molto sangue, qualunque programma si usi...