i'm not sure if it can do the job, but isobuster might be worth a try. I know it can often recover damaged data, but I don't know if it keeps track of deleted files as well.
generally any recovery program is banking on you being desperate enough to pay whatever they're asking...especially when the program can SHOW you the file but won't let you at it.
I went through the same frustration with some hard drive issues a while back...never did resolve it. just chalked it up to bad luck and reformatted the drive. (hope i'm not being too discouraging!)
i'll certainly be checking back in this thread to see if there are any good (and free) recovery programs out there...