policies regarding internet/email/computer use needs some flexibility

Thanks to Mr L for providing the title for this discussion.
I work for a large global company which has a “zero tolerance policy” towards “inappropriate use” of computer and computer equipment.
At our site, we maintain and service @450 pcs and @50 servers. We have recently acquired sufficient monitoring tools to identify those users who are abusing the trust our location has put in them.
What would you do if you found inappropriate but legal use going on your network?