If the partition table is damaged or missing then Recuva cannot recover files although I think it should be coded to handle hard drives in such situations.
I had a similar problem with a damaged flash drive Recuva wouldn't go as far as deep scan my drive and all of the freeware recovery programs I've tried had failed.
The only tool I had success with was DiskInternals Partition Recovery but it's commercial and the demo version only allows file previews, however it does gives you some idea just how much data can be recovered if any.
There is another program called "Roadkil's Boot Build" - http://forum.piriform.com/index.php?showtopic=26869 it can be used to write a new partition table however since I haven't used it and cannot comment on it's effectiveness.
When simply deleting a partition (without additional wiping) disk management software only removes the references to it in the Partition Table, thus leaving the possibility to recover it later. The Undelete Partitions Wizard enables you to find and recover these partitions. A restored partition will be fully functional, as long as other partitions were not created, moved or exceeded the disk space.