Short version

• I probably need software to run a deep-scan recovery (ideally on Linux) to find files on NTFS filesystem.
• The file data is intact, but the references are no longer present.
• Analogous to recovering data from a "quick-formatted" partition.
• Hopefully there is a smarter way available than deep-scan, one which would recover filenames and possibly paths.

Long version

I have a 3TB disk containing a load of backups. Windows 7 SP1 refused to detect the disk when plugged in directly via SATA, so I put it on a USB/SATA adaptor which seemed to work at first.

The SATA/USB adaptor probably does not support disks over 2.2TB though. Windows first asked me if I wanted to 'format' the disk, then later showed me most of the contents but some folder were inaccessible. I stupidly decided to run a CHKDSK on my backup disk, which made the folders accessible but also left them empty.

I connected this disk via SATA to my main PC (Arch Linux). I tried:

• testdisk
• ntfsundelete
• ntfsfix --no-action (to look for diagnostically relevant faults, disk was "OK" though)

to no avail as the files references in the tables had presumably been zeroed out by CHKDSK, rather than using a typical journal'd deletion).

If it is useful at all, a majority of the files that I want to recover are JPEG, Photoshop PSD, and MPEG-3/MPEG-4/AVI/MKV files. If worst comes to worst, I'll just design my own sector scanner and use some simple heuristic-driven analysis to recover raw binary blocks of data from the disk which appears to match the structures of the above file types.

I am unfamiliar with the exact workings of NTFS but used to be proficient at recovering FAT32 systems with just a hex-editor, so I can provide any useful diagnostic information if you let me know how to find it!

My priorities in ascending order of importance for choosing the accepted answer:

• Restores directory structure
• Recovers many filenames in addition to the file data
• Is free / very cheap
• Runs on Linux
• Recovers a majority of file data

The last point is the most important, but the more of the higher points you match the more rep you'll probably get :)