Your best bet -
Create new Domino Directory (called namesnew.nsf) use the PUBNames.ntf template. Then copy all the Data into the new Directory. Then shut the Domino server (service) down and replace the Names.nsf with this new DB (rename where appropriate).
This rename of the names.nsf would need to be done for all servers in your environment.
Not pretty but at least it would work.