My impression is that if you want to track your users' movements, the users you generally want to track are capable of circumventing simple measures like this. Note that the shell only records what is typed into it. I can use special file-system flags to make it so that the history file can't be deleted, and can only be appended, but you're right: there's nothing to stop them from running their own shell, or writing a simple shell in Perl, completely circumventing this. The only way to "reliably" do this is to do it closer to the OS-level, which is why most Unix variants support process accounting here.

The original poster should note that what he's trying to do is hardly novel or original, and most any major company's data center will have security policies requiring such accounting, and have generally thought of ways to do it securely. I'd avoid rolling my own, as this is definitely an area that you want to build upon the work of others, as there are a million little things you have to account for or else your installation is vulnerable to being circumvented.