Not sure exactly how your network is set up. One thing, though, if you are using the server directly, actually sitting at the server console, then any file or folder you delete will go to the recycle bin. For some reason, which only Microsoft can explain, if you delete the file across the network, then it will not go to the recycle bin. I NEVER delete a file from the server from a client computer unless I ABSOLUTELY know I don't need it.
If you are using Windows 2003 Server or SBS 2003, then you can enable VSS. This will automatically back up every SHARED folder up to 64 versions while running. You can set this to any amount of time. The default is twice daily.
Using VSS coupled with daily backups, should keep you safe. The nice thing about a server/client system with a domain is the permissions. You can set them so that users do not have access to modify the folder, only to read/write. It has been my experience that accidental deletion of files doesn't happen that often.
If you are using a non-server OS such as XP or 2000, You could purchase a Mirra Server from Seagate. This is a standalone server (basically a hard drive except it does contain a built-in OS), which backs up any folder every time a change is made. The problem I have found with the Mirra, at least with the version I have, is you can't set the time interval, therefore it is only helpful if you discover the problem rather quickly.
Vista has VSS built in, so most folders have previous versions. Just make sure it is enabled in Control Panel -> System -> System protection. I believe XP only allows a snapshot of an entire drive and does not make previous versions of individual files and folders available. One good thing about Vista over XP.
