I'm no lawyer, but I would think the purposes for which they read your email and the actions taken subsequently are blatantly illegal, and would invalidate the entire contract.
Yes, but severing would end up in court versus a very belligerent party, who would do their utmost to cost you money. An organization that prioritizes safety over ethics will just suck up the extra cost, apparently.
There are companies and organizations out there fighting for what’s right in courtrooms. Invalidating troll-owned patents, striking down unfair contracts etc. Agency A was obviously not one of those organizations.
Also, not legal advice, but you absolutely should name and shame them for this
Yes, especially since this sounds like a government agency. Some contractor snuck a backdoor into your email servers and is secretly reading them? Imagine what kind of corrupt practices, up to and including foreign espionage, that they could get up to. They could have been justified in sending in the FBI or CIA if this was the US. Probably would have put a stop to their vendor problems really quick.