You can't preserve a mailbox address in a move between sites. X.400 addresses are deeply embedded in all Exchange Server 5.5 objects, and mailboxes are no exception. When you move a mailbox between servers within a site, Exchange Administrator can rewrite the addresses for you. However, Exchange doesn't offer an automatic way to move users between sites because Microsoft never saw it as something users wanted to do and because of the technical problems of transferring mailbox contents in a reliable way between sites.

If user A moves from server A in site A to server X in site Y, any stored mail on server A that refers to user A will have an incorrect address.
To correct the address, you must either use Exmerge or manually export the mailbox contents to a Personal Folders (.pst) file, delete the mailbox, and recreate it on the target server. When you move an entire server, the Move Server Wizard uses the X.500 proxy redirection address to solve correct addresses.

If you use deleted item retention on all our mailboxes, moving users to a new server will result in the deletion of their deleted items cache. This behaviour occurs by design. When you move a mailbox to another server with the Tools, Move Mailbox command in the Microsoft Exchange Administrator program, Exchange removes that mailbox's items from the deleted items store. Microsoft implemented the feature this way to prevent unnecessary moving of outdated items, although the result can be disconcerting if you don't expect the deleted items to disappear.

The most recent version of the Exmerge utility (available from Microsoft Product Support Services - PSS) offers an option to move a mailbox while preserving its deleted items stash; if this capability is important to you, contact PSS to obtain the software.