I was messing around with a few ideas like using an AutoHotkey script to intercept delete actions and turn them into move actions. Shadow Copy holds potential but doesn't seem to quite fit the bill.
Finally found this neat trick on another forum which leverages special folders in user profiles. I tested it out a bit and it works surprisingly well.
1. Map a network drive to the network share you want to use. Make sure that the drive is re-connected on logon. If you don't know how to do this, search Google.
2. Browse to C:\users\<user name>.
3. Right-click on one of the folders in this location (I chose saved games) and click properties.
4. Select the Location tab.
5. Click Move, browse to to root of the drive you mapped in step 1, and click Select Folder.
6. Click Ok and click yes in the dialogue box that appears.
7. Repeat these same steps for all users on the computer.
You can now verify that the network drive is protected by the recycle bin by right-clicking on the recycle bin and clicking properties. The network drive should be listed in the Recycle Bin Locations column.
1. This only protects files accessed through the mapped network drive, and not by UNC paths. So for example, if you mapped \\server\share to z:, and delete something off the z drive, it will go to the recycle bin. However, if you browse to \\server\share and delete a file, it will be deleted directly.
2. I don't know what will happen if your network drive is not available, so beware. This may not work well with laptops.
3. What ever files that were supposed to be stored in the folder you select in step 3 will now be stored on your mapped network drive by default. This can actually be quite useful.
I don't currently know how to add this functionality to additional folders. As far as I can tell, only folders stored in C:\users\<user name> get this functionality. I'm still looking into this, but will update this post if I find additional information.