Cannot delete legacy mailbox on Exchange 2010 - Access is Denied
Issue
Some mailboxes on Microsoft Exchange 2010 cannot be deleted via Exchange Management Console. Following error is displayed:
Active Directory operation failed on <domain controller>. This error is not retriable. Additional information: Access is Denied. Active directory response: 00000005: SecErr: DSID-033520B4, problem 4003 (INSUFF_ACCESS_RIGHTS), data 0
The affected mailboxes seem to be those that were moved during Exchange Upgrades from Exchange 2003 > 2007 > 2010.