SharePoint MOSS 2007 has a nice two stage recycle bin which should cover one should anything get deleted accidentally. However there are cases when the recycle bin lets us down and throws a ‘File Not Found’ error when restoring items from the recycle bin. I experienced this recently and was lucky enough to find the cause and cure.
One possible cause for this error is when you are restoring items deep in a folder structure and the parent folder(s) have also been deleted. SharePoint is not smart enough to create placeholders for the parent folders prior to restoring the deleted item; it just gives up and throws an error.┬á To remedy this problem, restore the deleted parent folders from the Recycle bin first, then the restore of the child folders and files will now work.
If you do not know what the parent folder was you might need to restore the content database from its last good backup.