Recycle Bin for Network Share

I believe that doing this will allow users to delete files from their desktop/documents folder etc, and still provide a way to restore from the recycle bin.

I can confirm that with Folder Redirection, Recycle Bin still works on Windows 2008R2. Probably works on 2012 as well. But Folder Redirection and WinXP clients for example, Recycle Bin does not work.

Are there any other recommended ways to provide access to shared folders on a central server, which are not permanent deletions?

I think Shadow Copies is the way to go but maybe I missed something. There are some NAS which provide a "trash" folder where deleted files go.

With Shadow Copies (and probably also with 3rd party utilities), users can restore files without administrator interventions (See http://www2.slac.stanford.edu/comp/winnt/backup/vssrestore.htm for an example of how to do this as a user).

There are other 3rd party utilities which I personally have no experience with such as Undelete which is a Recycle Bin for File Servers.