> "do you know how many people we'd have to fire if we went looking for abuse?"

I think they make the mistake of presuming this has to go up to 11 on day 1.

Tell the employees you're going to be proactively auditing. Choose a threshold. Interview and potentially fire those employees going over the threshold. Do this until you're done firing people, then increase the threshold and repeat. You will have to fire people, or threaten to, but employees will get the message that the PII-party is over.