The reason I ask is that on VM only systems I like to disable automtatic alias generation in Unity (in the template) and just manually enter an alias when creating mailbox. I like to use the extension/mailbox number for the alias. That way the phone number, mailbox number and alias are all the same. As you know you can't change alias in Unity since it is actually an AD object. That way you never have to delete the mailbox - just change the name when a new user takes it over and delete messages - this applies to VM only.
I know of no way to change alias without deleting and readding mailbox. However you might be able to do it without losing messages from AD User and computers - delte mailbox in Unity first, then see if you can change alias in AD side then import VM box back into Unity. Messages should still be there. Right now I don't have access to test this for you. Sorry, I know you are looking for an easy way but there really is none I know of.
Since you are moving to unified messaging later in the year you are looking at a rebuild anyway and you will then be importing all mailboxes from Exchange - once that is done you will never have to worrry about this again since AD will take care of alias name generation - your life will be much better.