In Windows Settings | Accounts | Access Work or School, you have to make sure that not only is any applicable MDM package there, but also that it is connected to the Azure AD account. If not, you connect it, and voila, you're done.
Your users might not thank you, since they will have to re-setup any SharePoint and One-Drive synchronizations, re-install Office, etc., but it is what it is.
Best Response confirmed by
msalb (New Contributor)