I guess the main issue here (past all the social nonsense) is one user can affect another. This is a technical situation that Linux has been fairly good at preventing for a fairly long time. The fact this is a problem suggests to me that you're not actually providing these people with their own logins, going for a single-user method.
That's a major issue in itself because people using browsers aren't getting the privacy or security they might expect. People can run things in that shared user that log keystokes, monitors browsers, etc. Not good stuff.
So break things out. Get a LDAP-style system in place so every user has their own account. Make the computers refresh from a central ISO. User files stored in a central place too. It's hard work but it's infinitely better than what you've got.
By this point you're in a situation where no one (non-admin) user can affect another user.
Past this if people want to muck up their own sessions, you have to explore the behaviour that leads to all this. People are vandalising the lab equipment and you need to address that lack of respect.
A few suggestions:
- Log common commands that cause issues (easy with a wrapper script). For instance it should be posible to log the start of the accessibility applications to a central server so that you know who is loading it and when they're doing it.
- Charge people to fix deliberate breaks.
- Stick up a couple of cheapy webcams in labs to corroborate logs.
You don't need to get 1984 on your users but they need to know the limits.