You need to point the person docs to the correct mail file on correct server (i assume all the users are pointed to one server)
You should delete the mail files for the users that are no longer on that server.
The admin program to move the users will assist in the process and update the users location docs.
Don't bother with re-certifying the user id. if access to the other server is an issue you can accomplish the thru network access or allow access groups