Yo uso el Easy Recovery 6, siempre me ha dado excelentes resultados y es muy intuitivo (lento, pero eso como todos). También puedes echarle un vistazo al Hiren's Boot CD, lleva un montón de herramientas. Pero sigo recomendándote el Easy Recovery. Eso si, es de pago.
EDIT: En el GetDataBack no sé como será, a lo mejor es como el Easy Recovery y te permite filtrar por extensión. Por lo tanto podrías filtrar por *.avi o *.mkv según el formato de los ficheros que buscas. Así de todo lo que haya encontrado te filtrará esos datos. Además incluso si ha perdido el nombre original por el tamaño y la fecha podrías hacerte una idea de si realmente es lo que buscas.
Suerte!