This is due to the Microsoft ‘s permissions structure.
Since the deletion can be actioned in three different ways, the denial needs to be applied as followed:
1) Deny Delete (Object Class: User);
2) Deny Delete User Objects (Object Class: All Classes);
3) Deny Delete Tree (Object Class: User);