Microsoft Graph API: EntitlementGrant being updated or deleted is not found

We have an AAD Application with several app roles and we assign those roles to users. A couple days ago, we started to receive errors on the Graph API when we try to delete certain assignments. The error looks like this:

    "error": {
    "code": "Request_BadRequest",
    "message": "EntitlementGrant being updated or deleted is not found.",
    "innerError": {
      "date": "2021-04-16T11:33:23",
      "request-id": "someguid",
      "client-request-id": "someguid"
    }
  }

This error only happens on certain assignments and not for all. Also, we are able to delete them through the AAD UI. We are using the REST endpoint to delete the app role assignments and not the SDK.

What we have done so far:

• Changed from deprecated Azure AD Graph API to Microsoft Graph API
• Changed from endpoint users/{id}/appRoleAssignments/{id} to servicePrincipals/{id}/appRoleAssignedTo/{id}
• Issue is reproducible on 2 different Tenants / AADs
• Tested also with SDK, same issue
• Running the code locally works, but deployed on Azure throws the above mentioned exception. Using the same Service Principal locally and on Cloud to do the removal.
• Using AzureAd.Standard.Preview Powershell module also works (with another Service Principal)

Any help is appreciated