After deleting both the email account and the user certificate (we use certificate-based email authentication), I am unable to re-add the Exchange account back (after defining all credentials and parameters, I get a popup that says "Couldn't finish. Can't connect to server."). Additionally, I see a white triangle with an exclamation point inside in the notification bar. When I pull the bar down, the exclamation bar has a caption of "Network may be monitored by an unknown third party". When I click on that caption, I get a new pop-up saying "Network monitoring. A third party is capable of monitoring your network activity, including emails, apps and secure web sites. A trusted credential installed on your device is making this possible". There is a button underneath called "Check trusted credentials" and clicking on that takes me to a "user" portion of the trusted credentials store, where I see my corporate CA certificates.
In general, the issue of certificates issued by a non-public CA generating a "Network may be monitored" message has already been documented in several forums and there is an issue #62076 created for it. However, I suspect that "security features" introduced in KitKat are somehow preventing my device from using my certificate for email authentication (because device does not trust it). I knew I could count on Google to break the most used feature of my phone (email) and thus render it useless. Another win for the history books.