The thing that doesn't make sense to me is if there was pretty clear evidence that some vendor had put in a backdoor into the email servers of multiple government agencies and there were directors and managers at all of these agencies that had good reason to believe they were being spied on, then this would have warranted a criminal investigation of the contractor. At that point, voiding the contract, migrating to whatever other email service you have and getting out of the bill would have been easy. It wouldn't have mattered what sneaky language got slipped into the contract by the vendor, you do not ever get to spy on internal government emails.
The issue is the will to fight it, basically. Even if you're wronged, if the other party is belligerant you need to be willing to push for the criminal investigation, push for the transfer, defend yourself against lawsuits even if they're frivilous, etc. Many people in these organisations just want a quiet life and will bend over to such behaviour because the demands are not bad enough to make them want to fight it.
Perhaps you're right that it's government agencies (I may have even skimmed over a mention confirming that?) but my assumption, especially after the author mentioned one of the "agencies" being about 500 people total, is that he's more likely talking about something like a marketing or design agency, or a talent agency, or... something.