I kind of like spyder's answer here, except that I would not assume guilt, since this can get you into legal troubles. The way to attack this is multi-fold. First you need to create a policy stating that end users are forbidden to clear Internet History, event logs, etc... from their system without prior managerial concent. If the policy is violated you revoke their rights to Internet access for a month. Most will comply after that. In addition to the ISA server you will probably want to install a system to monitor and restrict access to questionable sites, and receives daily updates for acceptable sites. You will also need a logon banner stating that system usage is monitored, and don't forget the appropriate acceptable usage policies signed by the employees.

Don't mean to sound like I'm rambling here, but these are most of the things that companies have to do in order to protect themselves from lawsuits. All it takes is one sexually explicit picture viewed by the wrong person at the wrong time and you will find youself on the wrong end of a litigation process. Just IMHO.