Do off hours when no email is flowing
Replicate all nabs to one server and run a simple agent on each doc type to change the domain field
Replicate changes to all servers
You will need to restart each server for domain to take.
You need to send out a button to each user to change the location docs in the personal nab to change the domain field and possible person docs.
Do you have any apps that might contain the old domain name? Those will need to be changed as well
Here is a technote http://www-01.ibm.com/support/docview.wss?uid=swg21089340
One thing I always did when merging domains was to setup a Foreign Domain document for the old domain. That way if people did a reply to or never ran the button for the person doc/location doc cleanup the emails will go into the database specified in the foreign domain doc. You can create a agent that takes the docs in that db and modifies the 5 fields (sendto, copyto, blinkcopyto, from and recipients ) and writes the doc into the mail.box and marks the doc fixed (new field)