We are using the basic Office 365 Mobile Device Management and last week it started blocking half of our devices (mix of different iphones and android), including my own. There was no change made to the security profile or the mobile devices. I was in contact with support for 2 days and at the end I was told that there is no way to see why the devices are blocked without paying for the full Intune service, is that correct?
I'm not aware of any change made, but then again I dont deal that much with MDM nowadays. In any case, the answer you got from support is c*ap. Ask for the issue to get escalated and properly addressed. If there is a breaking change that now requires you to pay for additional licenses, you should have been notified well in advance, at the very least.