We run Deepfreeze in our library and its cut out all of the problems we were having. Very solid product, but a little spendy. We will probably deploy it a bit more widely when we go to Windows 10.
Locking down the machines is fine if you don't get any privilege exploits that take over the machine. Plus, this puts the machine in a known, good state every time we reboot or have a new user.
Cannot use Linux (I would use PC-BSD given our BSD infrastructure).
As another option, assuming you can use Linux, could go down the route of using Tails or another live distro:
https://tails.boum.org/