So you have a 360 GB drive that had a bunch of data and then you over-wrote the first 250 GB of its space to create a new Primary Partition, Format it, and write a whole new set of data there. Then you ran an Undelete operation on that 250 GB Partition and have found references to some of the old files, but can't actually get any of their data back.
Bottom line appears to be you MIGHT get a little of your old data back, but not much, and the odds are not good.
A File System uses several data structures to track what files exist, where their fragments are and in which order do they fit together. I understand that nobody outside of Microsoft really understands ALL of the details of NTFS, and I certainly don't. But for a rough idea of the process, the older FAT32 system did this. First level: there is a Partition Table at the start of the disk with details of exactly what contiguous blocks of the hardware device are assigned to which Partition; each Partition is treated as one "drive" by the OS. Next level (in each Partition): there is a Root Directory of fixed size, plus a File Allocation Table. For each file listed in the Root Directory, there is a record containing the file's name, its size, a date or two, and a pointer to the very first Allocation Unit (group of hardware Sectors) containing its data. There also is a File Allocation Table with enough space to record data for every Allocation Unit on the disk. Each of its entries is actually the pointer to the NEXT Allocation Unit containing file data. The Last entry in the chain of records for a file contains a special character recognized as saying "there are no more Allocation Units - you've reached the end of this file." When you create a file, all this info is filled in. When you delete a file, the very FIRST character of the file's name in the Directory is replaced with a special character to signify this but all the rest of the Directory entry is left unchanged. Over in the FAT, all of the entries associated with this file are re-written to zeros, and that makes them available for use by anything else. At some later time as new files are written, the space in the Root Directory may be overwritten with a new set of info, and the available entries in the FAT (and on the disk data sectors) may be re-assigned and used.
When you create and use a Subdirectory, it actually is simply a special version of a File, and it contains the same type of info in the Root Directory. But the actual tracking of Allocation Units for the files in it are still done with that one central File Allocation Table.
An Undelete operation can work IF certain things happen to be available. First, the Directory entry must be there, so that if you simply can replace the special first character with something else, it has a valid file name again. Then based on the length of the file and its FIRST allocated sector as detailed in the directory entry, the Undelete program can examine the FAT. It has to make an ASSUMPTION, for one thing. It will assume, because it has NO other info to use, that the disk sectors that originally were assigned to the file were just in one long continuous string. So it will look at the FAT entries, starting at the first one (from the directory record), and see whether there is a long string of entries marked with zeroes (meaning they are not in use now), and whether the length of this string matches the calculated disk space needed for the know file length. If the answer is yes to both, it can create a new set of entries in the FAT based on the assumed previous data and your file is restored. Well, maybe - there is no guarantee that the allocation sequence really was as assumed!
So, look at your particular case. You had data on a 360 GB unit; most of it would have been placed in the early part of the HDD, but some might be in the last 100 GB. Then you re-wrote the Partition Table, wrote a new blank Root Directory and Allocation Table for files, and filled in a bunch of data in those structures. In the Allocation Table all of the entries would have been reset to zero to show them ALL as available. Likewise the root directory would probably have been re-written to blanks before filling it up again. But even if it were not blanked out to start, all of the old data there pointed to the starting points of each old file in an Allocation Table that had been zeroed out! So, even if old file names existed, there is NO record of where they were! And of course, there's still that last 100 GB of physical space for which there is NO reference info at all!
A good file Recovery program starts by using those simpler pieces of info. But at some point ti might resort to examining every unallocated disk sector and looking for non-zero data. If it finds a sequence of sectors containing data, with blank sectors before and after it, it could offer that as a potential file. But the software alone can't know whether it's a file or not, or how complete it might be. That takes a trained person to examine and decide. And if any one old file actually is recovered as three or four such sequences in different areas, fitting them together is part of a giant data jigsaw puzzle.
Bottom line is you cannot find software to do the whole job on a disk unit that has had significant data over-writing going on. And the expensive expertise you can hire will only be able to find a small part of your old data. How successful they might be depends heavily on how fragmented your old files were before the disaster.