Updated 01/02/22:
For Samsung Galaxy devices with Android device administrator (DA) management or Android Enterprise personally-owned work profiles, a fix was released in December 2021 (CP Versio...
Updated Dec 19, 2023
Version 11.0
Blog Post
We've been having this same issue since around October. It was happening with new Android (Samsung) phones as well as ones that rebooted after a security update. All of the devices were registered under Device Administrator. I read someone else got it working by assigning Intune licenses. (We were using the free device management from Office365 for most users.)
As a test, I added a few MS365 licenses instead of Office365 (both E3) and sure enough, all of my non-compliant Samsung phones shows compliant. So there is definitely something up there. It's not affecting Google Pixel or Motorola phones. It's don't understand why licensing fixes it.
<opinion>
This is something the vendors need to work together on to create a fix for the existing platform without having to purchase additional licenses.
</opinion>