I hope somebody has an answer now. We have the same issue as E Jackson's have/had.
We've migrated from Exchange 2007 to 2013. Now only the Exchange 2013 available and the 2007 has been eliminated.

When I try to delete an address list from ECP or EMS (with 'Run as Administrator'), the output is:

Active Directory operation failed on dc1.domain.local This error is not retriable. Additional information: Access is denied.
Active directory response: 00000005: SecErr: DSID-03152501, problem 4003 (INSUFF_ACCESS_RIGHTS), data 0
+ CategoryInfo          : NotSpecified: (:) [Remove-AddressList], ADOperationException
+ FullyQualifiedErrorId : [Server=EXCHANGE,RequestId=24c0fea5-8ef6-4920-9c4b-2b4f3c0bd2cd,TimeStamp=2015.06.18. 10:17:49] [FailureCategory=Cmdlet-ADOperationException]FB6919D5,Microsoft.Exchange.Management.SystemConfigurationTasks.RemoveAddressList
+ PSComputerName        : exchange.domain.local

The user which runs the cmdlets is in the a Domain Admins group and in the Organization Management group as well.

Output of get-exchangeserver echange | fl admindisplayversion,exchangeversion:

AdminDisplayVersion : Version 15.0 (Build 1044.25)
ExchangeVersion     : 0.1 (8.0.535.0)

The ms-ExchVersion attribute in ADSIEdit is 4535486012416.

Has anybody solved this kind of issue?

Hi

can you check if your account has inheritable permissions checked in AD?

The inheritance is disabled now.

I read that in some case it helps, but when i checked it and tried to apply that it enabled, a warning appeared, that 70 permissions being added to the ACL. I do not know the exact effect what will happen if i enable it. How can i reset if it does not work. So i don't want to be a brave admin, first i have to know what i am doing.

I think your problem has to do with the "Exchange Trusted Subsystem" AD group doesn't have permissions to the AD object you are trying to delete. I ran into this same issue on AD objects in a delegated OU.

You can test this out by checking the permissions on the DL you are trying to delete through AD Users and Computers.  If "Exchange Trusted Subsystem" is not listed then you can add it.  For test purposes, give the group full control to the DL.  Wait about 15 mins for replication to take place and then try again.