I am always fascinated when trying to understand the mind behind the LDAP DIT designer. Yes, decades ago, the father of the LDAP were expecting that LDAP DIT is flexible enough to allow people to utilize the OU, so that people with the same name can reside in different OU without modification in his/her name, presumably that they use CN for the DN. But, I thought a modern LDAP DIT designer ditched that idea. Although, Active Directory (AD) people is still using that design, and worse they inject a policy into the OU location. But, to be fair AD is for AD, not for LDAP. But, I still disagree with that LDAP DIT design, although that is the way the cookie crumble.
Now, if you are using LDAP, hopefully not AD, then I would recommend you to re-design LDAP in a way that no one will be changing the DN ever, ever, and ever. Yes, that could be an invention of an ID that is not CN, nor login ID. And usually, just because you tried to find a work-around, I am guessing that you do not have the authority to do that. But, at least you can relay this concern to your manager and let your manager take the risk of being blamed in the future. So, as you may or may not know, every LDAP entry has a machine ID. For example: IBM TDS/SDS: ibm-entryUUID, AD/ADAM: objectGUID or objectSID, SunONE: entryUUID (I do not have a chance to investigate the one from Oracle, but I bet they have it too), Novell: GUID, and Domino: dominoUNID. So, every time you delete the entry, this engine ID will be deleted and when you recreate another entry a new engine ID will be granted. Now, if you have current or future connections (links) that are relying on this machine ID, then those connections (links) will be screwed up.
The remedy is the moddn (or modrdn) that Eddie was mentioning. But, I believe you cannot perform moddn on an entry that has child entry in it, because the DN of those child entries contains the DN of the parent entry. That means deleting and recreating the child entries would your best bet. But, this option is not only non-desirable, but also a dangerous approach, because if there is error in the middle of the process, such as an LDAP socket closed (or other external forces), then the recovery process will be very complex, especially if there is a group (or role) membership that you have to deal with. (I cannot imagine a modern LDAP design where it is not allowed to link to machine ID and/or not allowed to have group (or role) membership that rely on the DN of an entry. Hmmm… unless the LDAP repository is being used as a database (RDBMS like) repository rather than a directory repository)
Yes, I use too many 'but', but I still hope you the best.