I recently experienced an issue where devices became un-managed after the associtated user lost their Intune license. I've spoken to Microsoft who confirms that this is expected behavior. In conclusion the affected users had to re-enroll their devices, even though the Intune license was re-assigned before the Company Portal was opened.
Anyone have experience upgrading from an EM+S E3 plan to an EM+S E5 for example? Will users have to re-enroll even if they're assigned an E5 license before the E3 license is removed?