I don't even think it's a user problem.
As a user, I should be able to empty my recycle bin whenever I want without
having to worry about deleting something that I shouldn't.
But I do agree with JL, it is a user education problem in the sense that users
should make backups.
I think your IT staff (if you have one) has a responsibility to make nightly
backups of files stored on network drives (and backups of files on the local
drives, too).