How to Recover Files from Deleted Partition

Somehow one of my partitions disappeared (I didn't even have the disk manager open, so I'm really not sure how that happened). The volume was simply deleted. It was an NTFS partition, created under XP and used from XP/7/Ubuntu.

One of the Microsoft KB articles suggested recreating the volume and running a dskprobe utility. I created and did not format the volume, same size, drive letter, all that. My system apparently (neither XP nor 7) doesn't have that tool.

Not thinking clearly (losing the partition was just another nicety on top of a few other computer messes yesterday), I decided to try other tools to recover the partition. In the process, I deleted it, quick-formatted it, and then recovered it using another tool. I think I over-wrote the backup file table in the process.

I know all the data is still present and valid: it's been untouched since losing the partition and I tried running a file-recovery tool, which recovered a few pictures in perfect quality out of the free space. Unfortunately, the main files I need to get back are some customized Linux disc images (ISO format), which just happen to be linked to my boot menu (boot-from-ISO). There's about a dozen, ranging from 50 MB to 4.5 GB in size (basic system tools and console to a fully customized, pre-installed copy of Ubuntu). I can get/make them all again, but I'd rather just grab the data.

So, summary:

Lost partition, lost file index table, know data is present and in perfect condition, need to recover files (names don't matter), ISO format especially.

I have and can work from XP, 7×64, and Ubuntu x64. I have plenty of free space on other partitions, enough to copy the whole missing partition even, certainly enough to store recovered files. There is no file-system/partition in the space holding the lost files at the moment.

Anyone have any suggestions?

Edit: I've tried a few free tools. I'd rather not spend money, but I may spend a little bit for a good tool.

This shouldn't be a difficult problem. The partition was 99.9% defragmented (I ran TuneUp 2010's defrag in forced thorough mode just a day or so before, and had only added a few large files, no deletes). All the files should be in nice neat order, all in a row. Prime candidate for data-carving, if there are any good tools that can do this.