I had similar problems and minor success with a freeware program called PC-Inspector:
There's only one major problem, if the disc you want the recover the files from is the only drive and therefore you have to install the recovery software onto the formatted space. In this case you might overwrite sectors that contain files that afterwards cannot be restored anymore.
A solution are tools that run completely from a removable media like a diskette or a cd/dvd. The Linux/Debian distribution Knoppix would be such a solution. It runs completely from a cd and helps to recover files, even from non Linux operating systems: