If you want to keep the old server name you could setup a middleman server. What you must do is setup another Exchange 2003 server with a different name possibly in a virtual machine. You then transfer all of the email accounts over to the middleman server using the move mailbox option in Exchange System Manager, this is the fastest and safest way to move the mailboxes so long as the servers are both online. Also transfer the Public folders across.

Once you have done that you can decommission the old server, ie uninstall exchange which removes it from AD and change its name. You can then install the new server to the domain using the old name and transfer the mailboxes and public folders back to your new server.

I think that Outlook 2007 has a server auto location feature so changing the server name may not be necessary anyway depending on you policy settings.

Oh and if get errors when attempting to move any of the mailboxes across from the old server you can run a database compact and repair. Just use the ESEUtil.exe app which usually fixes up corrupted mailboxes that refuse to transfer.