Edit: My original version of this post was not really worded well, but I've kept it if you're interested.
Here's what I did:
I had a 250GB drive formatted NTFS, that I accidentally ran mkfs.vfat on, which reformatted it to FAT32. I happened to have an empty spare identical 250GB drive and did a dd copy of the drive onto the empty drive. I set the original aside so I'd have it if I messed something up. From there I ran Recuva with only the find non-deleted files, which found only a couple files. Then I ran the trial versions of several of the paid tools that have the option to specify the original file system type, which found everything on the drive (well, there was so much stuff, it certainly looked like everything). I then tried the Recuva with the deepscan option and got the out of memory error.
Not wanting to pay if I could get Recuva to get the files back, I decided to do a quick format to NTFS in Windows 7. After doing that, I did a deep scan for non-deleted files. After the scan completed, almost all of the files it found were recoverable, and I was able to get back most of what I needed. Some of the files I knew I needed back were marked as unrecoverable by Recuva, which the free tools seemed to indicate were recoverable (but I couldn't tell since I couldn't actually recover them with those tools). I'm concerned that the original mkfs.vfat didn't really do all that much damage, but the subsequent format to NTFS was overwriting parts of the files I'd like to get back.
After the reformat back to NTFS, Recuva seems to be able to get back like 95% or more of my files, which is a really good thing. It's the last few files I'd like to get back, but perhaps even the other tools wouldn't be successful, and I'd be out $$.