Last time I did this I went for the simple solution - I picked the server up and moved it to the same location, then did move mailbox.
The server was backed up first to tape and then the tape stored safe in case something happened to the server which it was moved.
Another method would be to move the smaller mailboxes using move mailbox over a period of time, and then look for a solution for the larger mailboxes.
Simon.