that sounds very bad, you are lucky you were able to enter recovery menu.I doubt undelete prog will help and will probably make it worse as every thing is encrypted and on a non standard partition.ie not fat32 or ntfs, ext etc.If your program does find anything it will probably mess it up even worse as it will try to rewrite the file in a format you can see which would change encryption and it would no longer be sony signed.only option would be if there was a undelete homebrew prog for running ps3 as its the only thing that can read/write to your hard drive and keep it sony signed but it will be a long time before that kinda thing comes out.I would recommend do a full format and reinstall 3.41 as it may have left other smaller errors behind.
just thank your lucky stars you didnt brick it.I bricked a 60gb coz of update loop, read that formating drive might help but as there was no complete firmware on Nand as soon as I formated I had a brick as the hard drive data was the only thing keeping it booting at all, your case is very different though.have you traced the issue that caused the problem? was you using awesome filemanager or firmloader? they are dangerous apps if not extremely careful.I dont think jailbreak could do this as it only patches RAM, must have been something else?
as a quick test heres is something you could try : copy an insignificant savefile from your ps3 using filemanager or FTP, then play that game again using same profile, create a new save file in the game and then exit , go back into filemanager and replace the new file with your old one, its possible it would work as the user is the same and the encryption keys should be the same as its same ps3 and same hard drive, might be worth a try just to see if its possible to save some stuff,