Autodiscover Not working, thus not able to download the GAL

We are having an issue with Exchange 2007, Migrated from Exchange 2003.  It's a Windows 2003 64bit server with IIS 6.0.

Our issue is that we cannot download the Global Address List and, because of that, it's generating sync errors in Outlook.

When running "test-outlookwebservices" from the Exchange Shell, this is the output:

Id      : 1003
Type    : Information
Message : About to test AutoDiscover with the e-mail address Administrator@externaldomain.com.

Id      : 1007
Type    : Information
Message : Testing server email.domain.local with the published name https://email.domain.local/EWS/Exchange.asmx & .

Id      : 1019
Type    : Information
Message : Found a valid AutoDiscover service connection point. The AutoDiscover
           URL on this object is https://email.externaldomain.com

Id      : 1013
Type    : Error
Message : When contacting https://email.externaldomain.com/ received the error
           The remote server returned an error: (404) Not Found.

Id      : 1006
Type    : Error
Message : The Autodiscover service could not be contacted.

When running a test email configuration from a newly created profile, this is the output received:

Attempting URL https://email.externaldomain.com/ found through SCP
Autodiscover to https://email.externaldomain.com/ starting
Autodiscover request completed with http status code 404
Autodiscover to https://email.externaldomain.com/ FAILED (0x80004005)
Autodiscover to https://externaldomain.com/autodiscover/autodiscover.xml starting
Received certificate error with no error context.  Failing with cert error.
Autodiscover to https://externaldomain.com/autodiscover/autodiscover.xml FAILED (0x800C8203)
Autodiscover to https://autodiscover.externaldomain.com/autodiscover/autodiscover.xml starting
Autodiscover to https://autodiscover.externaldomain.com/autodiscover/autodiscover.xml FAILED (0x800C8203)
Local Autodiscover for externaldomain.com starting
Local Autodiscover for externaldomain.com FAILED (0x8004010F)
Redirect check to http://externaldomain.com/autodiscover/autodiscover.xml starting
Redirect check to http://externaldomain.com/autodiscover/autodiscover.xml FAILED (0x80072EE7)
Srv Record lookup for externaldomain.com starting
Srv Record lookup for externaldomain.com FAILED (0x8004010F)

Our current setup incorporates a trusted SSL certificate for the email.externaldomain.com in order to utilize Outlook Anywhere.

We also have a re-direct for all http traffic to forward to the https://email.externaldomain.com which might be the issue.

It seems as though the lookup internally should look up via an internal address not the external address, but I can't seem to change it, could it be related to the redirect?

I had previous issues with the GAL actually getting generated to the folders located in D:\Exchange_Data\ExchangeOAB\b14572a0-9281-4c9d-a715-aeb9c1ef598d and now there are files in that location.  Had to recreate the GAL and the Exchange OAB folder and restart services in order for it to generate.

Under D:\Exchange_Data\ClientAccess\OAB\b14572a0-9281-4c9d-a715-aeb9c1ef598d there are also the GAL files as well.

Under the OAB (Default Web Site) Properties in the ESM under Client Access, the URLs are set to the following:
Internal: http://email.domain.local/OAB
External: https://email.externaldomain.com

I appreciate all help in regards to this issue.

Thanks!