If they have it in cache the best thing to do is have them export it to a pst. Connect to the new exchange server and import it back into their new empty mailbox.
A longer way is to take the psts and put them on a share drive and use exmerge on the server to import it into mailboxes.