This object is not inherited anywhere in the configuration partition in Active Directory, I checked the ACLs on the Databases Exchange Org and the Active Directory containers in between.
The following error shows the mailbox permission in question in more detail showing it is not Inherited. It also shows the error message we receive when attempting to remove it:
WARNING: Can't remove the access control entry on the object "CN=ceo,OU=Civic Centre,OU=CEO,OU=Office of CEO,OU=Users,OU=COMPANY,DC=DOMAIN,DC=LOCAL" for account "S-1-5-21-3350901170-1262693169-1119774923-3651" because the ACE doesn't exist on the object.
The same error is also experienced if we include "-InheritanceType All" on the command.
After reading into this a bit more, some people have posted that using the Exchange 2003 management tools allows the object to be removed.
I do not believe building a WinXP machine and installing the legacy Adminpak.msi and Exchange 2003 system manager tools is the way to go!
After scratching my head for a while, it turns out that adding "-Deny:$True" to the end of the command allowed me to remove the ACL.