For the binary "trusted or not" scenario can't you just have sudo-to-root? That tracks each user's actions (if they don't sudo -s) and gives the trusted/entrusted split. (bob can sudo but WWW-data can't).
- Linux Audit. Just have auditd tracing all execves. All execs made after UID transision (sudo su, sudo -s, what not) have a AUID appended that is filled with the original "logged-in-as" UID.
The bash shell, as of v4.1, can syslog every command, if you enable it at compile time. Very useful, we use it on all our prod boxes. Take all the other shells off the system and it becomes much harder for a hax0r not to leave an audit trail.
What I meant was that your group needs to have one "social" rule, "run all admin cmds under sudo, don't spawn a root shell and do it all there", for you to have effective tracking.