Recuva es el programa que yo he utilizado para recuperar algun archivo, en cuanto a nombres raros de archivos es normal, depende de cuanto hace que los has borrado, y del uso que le hallas dado despues al disco, desde luego, si borras algo, cuanto menos toques el ordenador, mejor.
La explicion a esto es que, el ordenador, cuando borramos algo, en realidad no lo borra del disco, simplemente borra su referencia, pero si lo usas, y el ordenador necesita escribir algo en el disco, quizas encuentre ese espacio como libre y lo sobreescribe, en ese momento si que pierdes la informacion.
Y como te dicen, es mejor que intentes hacer con algun gestor de particiones (gparted no recuerdo si tambien tiene esta opcion) copiar esa particion que contiene los datos a otro disco o sino a otra parte del mismo disco si se puede... y trabajar en una de las copias.
