Unfortunately, in the manner these files were deleted, the Ry-cycle bin did not have these files. On the QNAP forums and with what I mostly read - I was out of luck.
After a lot of research, I was able to recover over 66,000 files!!!
I thought I'd share my success and how to do this step by step.
My situation: 2 x TS-639's both with 1.5tb's running Raid 5 and EXT4. Firmware 3.2.5 Build 0410T
I do know, that running almost any style of hard drives (mirrored, raid etc.) will work, and MANY versions of the firmware back to v2. (linux 2.4.x - 2.6.x kernels)
Although this was done on a QNAP NAS, this will work on MANY brands of linux 2.4/2.6 based Intel NAS's. I don't believe it'll work on non-Intel based.
----------------------------
What you need:
1) An external USB or eSata drive large enough to hold your deleted data (more on this later) - Or if you have another partition that you can safety write to, this might suffice
2) Download and decompress on your PC/Mac etc. "Linux, kernel 2.6.x i386/x86_64 " from http://www.cgsecurity.org/wiki/TestDisk_Download
A couple of important notes:
1) Stop using your NAS NOW! The more files that get written to your NAS, the more files you will NOT be able to undelete. This includes even the log files that the NAS generates. I'd recommend turning off all services, applications and protocols except for the basic minimum (SMB, AFP etc.)
2) You MUST copy your undeleted files to the external USB/eSata drive. This program does not "undelete" like Microsoft where it restores the file where it sits, it literally re-writes the new "recovered" file - and thereby will overwrite the files you are trying to undelete.
3) Testdisk vs. Photorec : My partition was in tact and my goal was to recover deleted files only. In this case I'd strongly recommend using PhotoRec vs. Testdisk. Ignore the filename, as PhotoRec recovers MUCH MORE than just photos. If you are recovering from a deleted or corrupt partition - use Testdisk. Much of these instructions would also apply to Testdisk, although the specifics would change. The scope of this HOWTO is to undelete files using PhotoRec
Disclaimer: Obviously this isn't supported by QNAP - although if you ENSURE you recover your files to another partition or external drive, this process is also non-destructive to your existing partition as it only reads from your existing partition/hard drive.
-----------------------------
STEP 1 - Plug in your external drive, format it (EXT3 or 4) and make a directory to copy the uncompress TESTDISK/PHOTOREC files into.
STEP 2 - SSH/Telnet into your NAS, and find your way to the directory in which PhotoRec resides.

*You can see from diagram above that I changed to PhotoRec's directory "CD /share/USBDisk1/DISK/linux" on my external USB drive. The DISK directory is what I created on the USB drive, and copied the uncompress testdisk/photorec files & dirs into this
STEP 3 - Execute PhotoRec_Static package by using "/share/USBDisk1/DISK/linux/photorec_static" as below. Obviously replacing path with your own.

STEP 4 - PhotoRec will ask you to create a log file, say yes (this will be stored in the same directory you're in) - important that you've changed directory to the USB drive for this purpose
STEP 5 - Your hard drives will be shown as below. NOTE: You will see your individual drives - select accordingly if you're recovering from a single drive. Or as the picture shows below, select the /DEV/MD0 drive which would usually be your entire RAID volume if it's still in tact. Select your drive and use your right arrow key to highlight PROCEED and hit ENTER

STEP 6 - Select your partition type and hit ENTER. Photorec recommends staying with what it has determined on it's own and defaulted to. In my case it was "None". Although it also might default to "Intel"

STEP 7 - Pick your partition. In my case I had 1 RAID 5 formatted to EXT4, therefore it looked as below; (NOTE: Don't hit ENTER yet!)

STEP 8 - Using your right arrow key, move the bottom menu to "File Opt". You can also play with "Options" depending on your situation, although the defaults were fine for my use. I would STRONGLY suggest you spend a few minutes on this menu (as below) and De-Select the files that you are not interested in recovering. This will save a LOT of time in the recovery process. Use up and down arrow keys, spacebar to toggle. Press ENTER when done.

Step 9 - Select the EXT2/EXT3/EXT4 file system on the next menu as below

Step 10 - Important option here on the next screen. You'll have a choice of "Free" or "Whole" to scan. If you're recovering from a partition corruption etc. you'll probably want to do Whole. In my case just with file deletion, you will want to choose "Free" to scan for free space only. The Time difference (in my situation) was 320Hrs (Whole) vs. 8Hrs (Free).

Step 11 - IMPORTANT STEP! This prompt (below) is asking you where you want the recovered files to be written. Once again you do NOT want these written to your NAS unless it's on a totally different partition. I'd suggest either different partition or external drive. Use your right and left arrow keys to navigate to the drive where you want the files restored, then press "Y" to start the recovery process. NOTE: When you press "Y", the recovery process will start. In my case, it ran for almost 9 hours - obviously mileage will vary greatly depending on your options and situation.

This process will create automated and auto numbered directories and file names during the restoration process.
Note: Unfortunately your filenames and directory names will NOT be restored. I would install and use an indexing and search engine on your PC and use that to index files and contents of files- this helped me recover the files I was looking for.
I had great success with this process and tool, with restoring over 66,000 files.
I hope this helps someone else in their moment of panic!
Feel free to email/respond if you feel my experience can help you in any way.
Cheers!
News