I accidentally deleted my "TV" folder with around 600gb worth of shows in whilst I was booting Ubuntu from a USB.
I permanently deleted them for the Trash.
I then booted into Windows, which is on a different HDD to the deleted files, and tried to recover.
I tried using lots of software such as;
Digital Rescue 4
PhotoRec in both Ubuntu and Windows
None of these found anything besides files from months ago. Considering the folder I deleted is 600gb, hasn't been re-written over, and only happened yesterday why aren't my files being found? Surely it should be easy to find them?
You are right, your data is still there and technically recoverable and your post brings back some bad memories of similar situations I've gotten myself into.
I as you had difficulties with some of the programs you list but was able to get through my predicament using Undelete. try clicking on the link and take advantage of the free trial being offered, hopefully it will work for you too.
In all honesty my accidental delete, although larger (1.2TB), did not come via booting Ubuntu so I don't know if that will make a difference but it's a free trial and something you haven't tried so there's nothing to lose.