Recently we started getting the below error suddenly in one of our environments for all the users.
“You need a Microsoft Dynamics 365 license to continue. You do not have a license to use Microsoft Dynamics 365. Contact your Office 365 administrator to assign a Microsoft Dynamics 365 license to you.”
The users had the required CRM licenses and this error was only coming for the case entity.
Eventually, we realized that a Plugin / Workflow was running under the context (owner for Workflow) of a user who had recently left the organization and had his account disabled inside CRM.
Updating the context and owner of the workflow to run under the Service Account (with appropriate roles) fixed the issue.
Hope it helps..