Move Mailbox only works between servers in the same site, so it isn't an option for you.
You have to create a new mailbox and (at least) hide the old. You can give the new mailbox the same SMTP address as the old mailbox after you have replicated the hide of the old mailbox to the destination site. You can also give the new mailbox an X500 address of the identity of the old mailbox, which will then allow replies to old mail to be routed to the new mailbox once the old mailbox is deleted (create a New, Other address on the new mailbox, type is X500 and the address is /o=<orgname>/ou=<oldsitename>/cn=<recipientscontainername>/cn=<oldmailboxdirectoryname> - obviously you need to replace the <variables> with the correct names for your installation, and make sure you use the directory names not the display names for each portion).
You could also add a rule to the old mailbox to reply with a message that says the person's mailbox has moved, and that the sender needs to resend the message but pick the name off the GAL this time - this will catch any replies to old mail or PAB entries before you finally delete the old (hidden) mailbox.
Mailbox contents can be moved from the old to the new mailbox either by exporting all folders manually to a PST, and then manually importing again, or automate the process using ExMerge.
Yes, I know all the above is a pain, try doing it for 20 users! Exchange 2000 and onwards fix this problem...