Keep in mind that in Notes, deleting a folder does not delete the CONTENTS of the folder; it just means that the documents are no longer associated with the folder. Therefore, you have not lost the documents themselves, but perhaps some organizational metadata.
Restoring folders is very easy with the Lialis Restore Folder lotus notes mail solution: http://www.lialis.com/lotussolutionprovider.nsf/pages/folderrestoretoollotusnotesmail. The solution keeps track of every folder and modification and the associated documents are stored with their document id. A deleted folder is recovered with just a single mouse click.
Did the problem already occured and the Restore Folders solution wasn’t implemented yet: Implement the Restore Folders application and ou only have to recover the deleted folder from a backup database and your user can copy his or her folders locally to the new database.
Test the solution yourself by implementing the free evaluation software (with full functionality), suitable for ten databases: http://www.lialis.com/Applications/AppDownloadStore.nsf/9b510713a120dbc6c12574da001953fc/a66521ad32463a73c12575360057d5ef?OpenDocument