Martijn Tigchelaar There's no conspiracy or nefarious subterfuge going on here. If CA approves the connection, then Exchange mobile device access processing is skipped and the device is marked with the following access state:
DeviceAccessState : Allowed
DeviceAccessStateReason : ExternallyManaged
With the change implemented in this article, those devices that were once considered externally managed are no longer such and now have Exchange mobile device access processing applied. That's why the devices get blocked/quarantine.
An app update did not change the device ID. What happened on February 2nd was that we increased the rollout to 100%. Your tenant had this policy change applied.