I recently managed to delete a folder of very important photos before they were backed up (to Mozy). Believing that the contents was backed up I formatted the card (high-level, camera format) and put it in my camera bag for use. When I discovered the disaster there was no way of undeleting or rescuing the files off the hard drive. In despair I tried rescuing them off the formatted card (which had luckily not been used).
In summary, using PhotoRescue Wizard 3.1 from DataRescue, I managed to rescue all the files (Canon EOS 450D CR2 RAW format) perfectly. The program lets you test if it can recover before you pay (29 USD) and is highly recommended.
I also got to test support since my card transaction was slow and they helped me swiftly. One tip though. DataRescue lets you choose between two e-commerce providers. My anecdotal evidence suggests you should use Kagi.