So, think about how you are blocking access to the Internet. For example, if you are requiring that your browsers simply configure their configuration to point to a proxy, are you still allowing traffic out through your Internet connection from other systems other than the proxy?
To clarify, what I am suggesting is that if you are forcing your users to use a proxy, then at the perimeter firewall, you should block ALL outbound traffic except from your proxy servers. This will force all clients to use the proxy servers to get outbound access.
Then, at the proxy server, you can impose the restrictions required for your users.