Seems like someone who would be doing something worthy of the surveillance you suggest would do more than retroactively delete .bash_history. For example:

HISTFILE = /dev/null

Just because there is the potential to have a bad egg using your computer, doesn't mean you have the right to invade users' privacy. I hope you have a banner warning users that their commands are being monitored as well as a policy describing appropriate vs. inappropriate usage of your system. It seems to me the method you describe is invasive; similar to police frisking every person that passes by, or maybe just taking an x-ray scan to store on file as evidence if some crime is committed later. I bet the ACLU would have something to say about that.

</soapbox> Nod, Andukar, I see where you are coming from. The whole thing just irks me. I suffer from latent libertarianism, apparently.