IE History Viewer obviously works only on Internet Explorer entries, but if your offender is an idiot who uses IE, then you will have him dead to rights.
If he's smart enough to cover his tracks with that (or uses Firefox exclusively), then I'd say get a firewall... most have the ability to log internet activity for you.
If you have a spare machine (even an old PII would work), then you could build your own firewall appliance with something like
Smoothwall Express.
Of course, with a firewall in place, you could restrict your users from having access to those types of sites, as well. Smoothwall integrates well with the
DansGuardian content filter.