1- Lugar intenta proceder a la recuperación de los datos con un software como File Scavenger, si con ducho software los archivos recuperado se hallan dañados poco o nada se podría hacer para recuperar los archivos en correcto estado.
2- Si has procedido a realizar un formateo del dispositivo con un software denominado Hard Disk Low Level Format Tool, y el problema también es generado atraves de S.O no desatendidos lo mas seguro es que el dispositivo se halla dañado.
3-Sobre buscadores, hay varias alternativas al estándar de Microsoft, como SearchMyFiles, Super Finder, Agent Ransack..
http://www.softonic.com/windows/utilidades-de-busqueda