I am not sure whether I’m missing something here, because on your earlier comment you said there is no birthright roles, but in the latest response I can see the role is configured with membership criteria which obviously considered as birthright role to the identities who is matching with the criteria. Considering that you have a birthright role, you can try the below options
- Add another criteria to unassing this role from identities to remove the entitlement during delete process. This may be an attribute which decides the delete operation.
- Attach the Access Profile to the role instead of direct Entitlement which I can see you already tried and its working.
- Check whether this issue occurs to all identities or intermittent, if it is intermittent, check the aggregation schedule and there might be a chance the accounts are deleted before the role revocation completed.
- Workflow Option: You can refer Workflow to remove ALL leavers' standing access and use GetAccess and ManageAccess Workflow actions to remove the specific entitlement.