Recuva is very efficient and System Restore does its job properly when it does it at all, withotu deleting the wrong kind of files. I deduce from that your files have not gone missing and that's why Recuva can't find them.
Go from Start to Run and in the Open box, type cmd then press Enter. You now have a black form with a Command Prompt. At that prompt, navigate to the folder that holds your personal files using this syntax:-
chdir c:\documents and settings\yourname
then press Enter. Substitute yourname with the name of your User Account.
You now need to type the following:-
attrib *.* -h
and press Enter again. Type exit then restart your computer. If my suspicions are correct and the files were hidden - perhaps by some malware which caused you to use System Restore - you should be able to see them. If not, please post back.