Once you're done, follow KBA 822931, which has step-by-step instructions to walk you through the process.
Firewall & External DNS settings: If the server being removed is accessible from the Internet on any ports/protocols like SMTP, POP3, IMAP4, HTTP/HTTPS, et al, you will need to make sure these settings are also implemented for the new server. You will also need to create a new A record for the new server in your external DNS zone, or modify the existing A record for the old server's IP address to point it to the new server's external IP address.
Once you're done and have tested all functionality on the new server (particularly inbound mail), shut down the old server for a couple of days. If all looks good, uninstall Exchange from the old server, and decommission the server.
This was first published in July 2006