testdisk is usually fairly good about finding things, but with the NTFS directory information lost by formatting the partition, I'd suggest you try foremost which looks for file signatures and can sometimes pick out file fragments for you to stitch back together. (This is neither fast nor easy.) The problem with Windows files is that they are quite often fragmented on your disk unless you defragmented quite often. (Most Linux file systems avoid fragmenting files unless your disk is critically full.)
There's also ntfsundelete, but I believe that that program is only usable if the NTFS is intact.
Suggestion: If you have the disk space, make an image of the problem partition (using, for example, dd_rescue) and then work with the image instead of the actual partition. (I.e., backup the damaged partition before mucking with its contents. One hopes you've now learned the value of a backup.)
Once you've got the partition backed up, you could try a Windows quick format on it (which should make it a NTSF partition with an empty directory) and then see if ntfsundelete can find anything there. (I think - but haven't checked - that ntfdundelete is part of the ntfs-tools package.)