Here is how I expect most viral programs accomplish it (but I've never purposefully made this registry change to any of my own computers so I don't stand behind it in any way, shape, or form). Make sure you backup your registry before deleting the following key:
Remove the registry key: [HKEY_LOCAL_MACHINE\SYSTEM
\CurrentControlSet\Control\SafeBoot]
This appearantly does not remove the boot menu. However, it disables Windows' ability to actually boot to safe mode and causes a Blue Screen of Death (BSOD) and restart.
I recommend testing it on one computer before implementing it in mass on what I am assuming are public access computers that you are trying to lockdown.
Cheers!