1) You missed a step. After the direct deletions you needed to still go to the Active Directory Sites and Services to validate that the replication object is gone from all sites.
2) You were not on the Infrastructure Master when you executed the steps. Check to see which server is the infrastructure master in your environment. Go to that machine and reproduce the steps in article 216498.
3) There is a problem with Directory Replication. If you have multiple domain controller and sites, you could have a problem with Directory Replication. You can use REPLMON from the Resource kit to check. Also you can use the Active Directory Sites and Services to force replication and then check the event logs for errors and issues. Additionally, check to see which servers are Global Catalog servers in your enterprise. If you have multiple sites, the importance of GC's in replication increases. If you do not have a complex forest structure (multiple domains) making all of the servers GC's is ok.