I take it you want to also change the mail domain.
Location doc
Person doc (public and local nab)
Server Doc
Connection doc
All needs to be updated with the new maildomain info.
Don't you also want to change the internet name with the new name as well? IF so I would add the old internet name in the fullname Field so outside user will still be able to communicate with these users. They can removed later on
For location and local person doc I suggest mailing all users a button to change all oldmaildomain to newmaildomain
All this really needs to be done at one time. If someone does a reply or does not click the button to cleanup contacts you can add the non adjacent domain doc that will collect the emails to the old domain. You then can write a scheduled agent that will change all references of olddomain to newdomain in the to/from/cc/bcc/recipients field and then compose a new message in the mailbox to send off the email.