I enabled Outlook Anywhere on the Primary external-facing Exchange server. But then some of the employees were complaining that whenever they would connect to exchange using Outlook that it would ask for their credentials. I chalked it up to being a permissions issue, but apparently the old Ex03 server was somehow still in the mix.

Open the registry editor on your Outlook Anywhere machine and checking the following key:
HKLM\SOFTWARE\Microsoft\Rpc\RpcProxy\ValidPorts
Make sure that you only see the name of your exchange server and the ports 6001, 6002, 6004 for the servername and servername.domain.tld.
I noticed that the old server was still listed in there. I deleted it, and then restarted the Microsoft Exchange Service Host to complete the task. Unfortunately the old server was put back in.

So then I checked ASDIedit and saw no traces of the old exchange server in the mix. Odd. So why was the old server still showing up in the RPC registry keys?

I had to load up IIS/Adminpak.msi on an XP machine to get Exchange 2003 System Manager to install (ESM). Loaded that up and under Admin Groups I could clearly see the old Exchange server. Booo.
Right-click, delete. *poof*.

Redo the registry edit steps and restart the service host service and bam, working again. Now no more complaints.