I had used a stripped down version of DamnSmallLinux (BoothCD) before but that didn’t work anymore due to incompatible hardware and I couldn’t be bothered to configure a new version.
The new computer already came with Windows Vista so I thought lets give it a spin. I was afraid that it would take a long time to setup SteadyState properly but the GUI is really quick and intuitive. So from download to finished setup it takes about 15 minutes (plus one reboot). You can configure the machine to not store any changes made by the kiosk user (which is what I used). The only thing that I had to do in addition was to hide my administrator user from the welcome screen.