We came across a strange issue with Microsoft InTune where one Office365/InTune tenant was working fine with iOS (native email app) and Android Gmail app using cert based auth for ActiveSync, but another exactly the same integration & configuration of Office365 and InTune/Azure AD instance was not able to connect with the Android Gmail app even though the Gmail app had the users identity certificate in the app and iOS native email app was able to connect without any issue using cert based auth via ActiveSync to Office365
After opening a case with Googles Android PACE team thanks to Gerard Kennedy @ Google, they were able to start the investigation and troubleshooting with Microsoft engineering team.
It has been confirmed that Microsoft had made a change their end which meant Gmail failed to interpret the server response correctly.
Gmail team have deployed and verified the fix for this. The fix will be in a future Gmail app update to be confirmed about release date and version.