A literal chicken-wire-style cage that encloses the PC case, with openings too small to pass the head of a USB device.
The cage would be locked to prevent removal of the machine and have a locked backpanel which allows certified staff to install the various usb devices -- with some sort of cage mount inside to loop the cables around, so that a tug from the user wouldn't pull the usb connector from the machine and cause an obnoxious number of calls to 'the guy with the key' to plug a mouse back in.
The cage would neatly deny access to any and every port or drive that may or may not be present in one fell swoop, which would likely simplify OEM contracts and final installation as well as increase security.
You could build the cage physically larger than the general range of whichever flavor(s) of ATX cases are being used, so that the cages could be manufactured in bulk without too much worry about a switch between PC OEMs causing problems.
You could even add a screw-style bracket or two to hold the PC case firm within the cage and put some acoustic foam pads here and there to cut down on any extra noise.