Thanks for the information, it makes no sense to me that Enterprise Admins don't have delete subtree for these account!
I've worked around it by adding a script to the scheduled task to grant the service account delete subtree permisison to the user before it tries to delete them. We still get an error the first time it tried to remove it, but the second time the account is deleted which works for me :)
In case anyone else runs into this, my script is
Import-Module ActiveDirectory
#Get the existing ACL for the user
$acl = get-acl -path "ad:%distinguishedName%"
#Get the details of the Adaxes service account
$user = get-aduser -identity <service account name here>
$sid = [System.Security.Principal.SecurityIdentifier] $user.SID
$identity = [System.Security.Principal.IdentityReference] $SID
#Build new ACL for the user
$adRights = [System.DirectoryServices.ActiveDirectoryRights] "DeleteTree"
$type = [System.Security.AccessControl.AccessControlType] "Allow"
$inheritanceType = [System.DirectoryServices.ActiveDirectorySecurityInheritance] "All"
$ACE = New-Object System.DirectoryServices.ActiveDirectoryAccessRule $identity,$adRights,$type,$inheritanceType
$acl.AddAccessRule($ace)
#Set the ACL for the user
Set-acl -aclobject $acl "ad:%distinguishedName%"