Join your new Exchange Server to the existing organization. Use the Exchange System Manager on the 2003 server to move the mailboxes since it’s multi-threaded, and will move 4 mailboxes at a time. You can also queue up all the mailboxes and just let it run.
Then move your system mailboxes, fix your connectors to use the new server. From that point, you should be able to remove the old server and everything should be happy. I would spread the activity out over several days so you don’t have the system and AD trying to do too many things at once.