If you remember way back in September of 2003, (I don't, had to look up the date), a new version of Exchange Server was released with a new and really cool feature, RPC over HTTPS. This allowed for use of Outlook outside the company's network without the need for VPN. What a huge boon for traveling employees and IT staff alike.
With that came a convoluted configuration that probably resulted in more support calls to Microsoft than anything else involving the then-new Exchange Server 2003 product. And I always found it puzzling that Microsoft didn't create a wizard to automate this configuration, as they did for Small Business Server 2003, which included Exchange Server. (This was addressed in the later Exchange Server releases, 2007 and 2010.)
In any case it always seemed like a miracle was preformed when RPC over HTTPS finally did work. Fast-forward seven years and there are web pages and tutorials aplenty. In my recent search, the MSExchange article I found was the most straight-forward for a single system, Exchange Server 2003 deployment. One key element upon completion of the feature install and changes to the registry, is to make sure you reboot any Domain Controllers that were updated after the work is complete.
The reboot is necessary to complete the Global Catalog port mapping of 6004. In fact, you should be able to telnet to ports 6001 and 6002 on the Exchange Server, and 6004 on the Global Catalog server that was updated.
And as always, there is the über-useful Exchange Remote Connectivity Analyzer to aid with troubleshooting (that's how I found out the Global Catalog needed a reboot).