We're using dansguardian with squid to block sites with *naughty* content. However, there really isn't any way to block all email and proxy sites. Heck, budweiser.com offers free email accounts. Anyone can setup a linux server at their home to accept/tunnel/etc.
What we do is implement office policies, and inform the users that we log (true) every single web page they visit. Then later, if a manager suspects misconduct, we can always pull up a listing of all sites visited, and discipline from there.
I'm sure there are people who abuse our system, but they all will eventually be caught. We make public examples out of abusers. It keeps everyone else honest.