This is pretty similar to what I did for some computers in our Student Center. They were WinXP machines with admin access. On a college campus. Shudder! I'm sure they had more virii than... well, you know.
After spending about 15 minutes trying to clean up the horrible mess, I decided to switch the machines to Ubuntu. At first we just had a "student" user that was automagically logged on, but we had some high school kids come in who had no problems standing at the computers for 3+ hours a day. So I created an .xsession script that made absolutely nothing start up except for my custom pyGTK+ script that gave them... I think it was 15 minutes, and then automatically logged them out. They could launch firefox and browse the web, but that was it. Once they closed firefox, my program would pop back up and lock the screen for 5-10 seconds (it's been a while since I've looked at it). This effectively annoys anyone who wants to stand there and just log back in, but that's about the time it takes for one user to move all their stuff, leave, and the next guy/gal to take their place.
Marco's idea is pretty solid, though.