So, this post of mine did generate some fun responses. While going thru them I remembered an old idea that I saw a long time ago on one of the security mailing lists, possibly firewall-wizards. Somebody suggested collecting all the web surfing statistics data for all the company users and posting it publicly (well, internally) for all to see instead of blocking.
Want to surf playboy.com in clear violation of the network AUP? Suuuure, help yourself, but be relatively confident that your boss will know about it. Surfing to a "hacking" site? Well, if security is your job, you should be.
This approach resolves the "false positives" challenge, inherent with "blacklist" filters and takes a now-fashionable community approach to security. At the same time, embarrassing people into action seems more efficient than threatening or failing while trying to block their access. What is even better, this approach does seem to "fail gracefully" unlike the "block and filter" approach since he latter, when penetrated, provides no benefit.
So, post the statistics per user, URLs, volumes, etc. Glance over the results and let others do the same. I am pretty sure that "inappropriate web access" will subside dramatically. Since we know we 'have no privacy' , why not use it to our advantage?