For some reason in outlook the GAL (Global Address Book) is not updating. And when. in Outlook you click to download the GAL\Offline address book it just sits there forever - I a have waiting over 8 hours and there is no progress. It seems as if the client is not connecting to the exchange server to get the OAB.
I ran Fiddler and saw that several client (Domain Users and Domain Admin) can tunnel to mail.company.org without issue. But they cannot tunnel to the FQDN of the Server name which it seems to want to do when downloading the OAB.