1.
Pull the Hard Drive. Stop using the hard drive immediately and disconnect it. Continuing to use and "write" to the hard drive can only cause more damage to your "missing" data.
2.
Professional Data Recovery. Yes, there are companies that perform data recovery; but I have no knowledge or experience with any of them. No, I don't know about "pricing", but I've heard it can be expensive. I've also heard it can "vary" quite a bit from company to company.
You need to decide what your "data" is worth and how much "risk" you're willing to accept.
3.
Do you feel lucky? Buy a new hard drive and reinstall the operating system. "Slave" the old hard drive to this system to see what you can see. Avoid all writes to the old hard drive. I've heard an internal connection to the motherboard is better than an external enclosure.
Try some of the more reputable "free" data recovery and/or partition recovery software to see where you're at. Remember, no writes to the "old" hard drive. You need to recover data to the "new" hard drive or other storage media. Don't hurry. Understand what you are doing before acting...
I've never looked for files on a system where the operating system had been reinstalled (and partition was possibly deleted, recreated, and then formatted).
4.
Reference(s):
a.
http://tech.icrontic.com/articles/advanced_data_recovery b.
http://www.cgsecurity.org/wiki/TestDisk c.
http://www.piriform.com/recuva