No, no mejor no formatees. Yo creo que el disco está "bien", no tiene errores graves, simplemente es un problema con el sistema de ficheros coruptos o alguna cosas rara de particiones y por eso los programas de recuperación de datos que has probado no te han funcionado (no reconocen la partición, no pueden recuperar nada). Perfecto si al conectar el disco externo por usb lo reconoce, eso es buena señal.
Por eso te recomiendo el TestDisk para intentar arreglar el problema:
- Programa
TestDisk (especialmente recomendado cuando hay particiones dañadas, no reconoce la partición, etc)
* Arreglar la Tabla de Particiones, recuperar particiones eliminadas
* Recuperar sectores de booteo FAT32 de su copia de respaldo
* Reconstruir sectores de booteo FAT12/FAT16/FAT32
* Arreglar tablas de booteo de tipo FAT
* Reconstruir sectores de booteo NTFS
* Recuperar sectores de booteo NTFS de su copia de respaldo
* Arreglas la MFT usando la MFT mirror
* Localizar el Superblock de copia de respaldo de ext2/ext3
* Recuperar archivos de sistemas de archivos FAT, NTFS y ext2
* Copiar archivos de particiones FAT, NTFS y ext2/ext3 eliminadas
http://www.elhacker.net/reparar-recuperar-disco-duro.html