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.
To be honest tho - this is the contract that both the company and union agreed to, so bad on the company for being okay and not making this a more serious infraction. I've talked to some of the union stewards about this and they basically said they wanted this data locked down harder. They said it's too easy to access and super temping and wished the company would put more protection around it. Go figure.
Yes.
Should you have been fired? Depends on how much you abused your privilege and what you did with that information. Your comparison to 1 strike laws and greater crime is pretty rich given the information you improperly accessed could be used to blackmail others, or whatever. It's important to treat such information with the utmost respect. Your cavalier attitude and inability to accept responsibility in this regard may be very common within the tech industry, but such attitudes are also why there is a growing movement to; take data out of the hands of companies, and to harshly punish companies who fail to protect the data on one hand while vacuuming up as much as possible with the other.