Little over a year ago, I had to do a very similar thing.

I had to move everyone to a new exchange server. Since I wanted least amount of impact on the users. I brought the new server on-line and connected it to the existing Exchange site, The new server gets all of its information from the old server.

Then over a period of a couple of days, I would move users from the old server to the new server using the move user tool. For windows outlook users this move was seamless since outlook will automatically adjust to point to the new server. I also moved all public folders and made sure that everything was working off of the new server, IMC and any other service that the old server might have been running.

Once everything was moved and running ok, I shutdown the old server... waited a few weeks for any complaints, and then removed the old server from the site.

Bryce