Why not simply create a background process
that every hour or so creates a (hard, not symbolic) link to the files in those important directories? (Say to a /saved directory). rm is only going to remove the file if all of the inodes are gone, and since an inode for the file exist (to /saved) the file won't be deleted.
Kewl thing is, all it costs in space is an extra directory entry. If you really want to have fun, this background process is owned by someone else and users won't be able to delete files through it. (They can overwrite files with an empty file, howeverm and the background process will pick it up.)