Wow a lot of ideas to do this. You can also do it if the user does not have rights to make changes to registry pretty easy.
First I would set them to go to proxy unless the web site starts with option and put in your pre-approved sites with a semi colon to seperate them. You can find this in the "Advanced" button in the connection tab under tools. Then to keep them from changing those, add these keys that will work in your particular case.
IE restrictions
In particular the NoBrowserOptions. This will not allow the user to open the tool menu anymore, making it impossible to change the proxy settings. In a domain or workgroup, this will work in a pinch for specific users since the proxy settings are based on per user, but the locking of the tools menu is machine wide. Just remember to set everyone's settings before you do the registry change.
Simple, free, and easy to reverse.
Good luck, I have people who try to do all sorts of things to get around the firewall and such. Now get off the forums and back to work!
Oh, and add this,
http://www.techjunkeez.com/archive/registry_hacks/disable_IE_clear_history.htm
then they can't erase their history....
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Internet Settings\Url History]
"DaysToKeep"=dword:0000000a
so they can't change the number of day to keep a history. (the key is by default in Hex, so you will need to remember to click the radio button for decimal if you don't know the conversions)