Paul,
It's actually pretty easy. All you need to do is add the exchange servers to the archive targets, enable the mail accounts, aggressively archive them, then disable the accounts, move the mailbox, and re-enable the accounts on the new exch server. There's some debate if the procedure actually needs to be that long, but it's the "safe" way to do it, and it's supported. Good luck!
micah