Update:Rebooting the server seems to have fixed the GAL "Add to Outlook" action. However, many of the email address in the Outlook SharePoint list contain personal email addresses rather their domain email addresses. I initially suspected that these users might have entered their personal email addresses in "My Settings>Account Settings>Reply-To Email Address" or "Backup Email Address" but all of the ones I looked at these fields either blank or in the case "Reply-To Email Address" had their domain email address. Nor for that matter was their personal email address to be found anywhere in the "Account Settings" or "Account Profile settings.
Looking at the ones with personal email addresses I'm guessing that they used their personal email address when setting up their smart phones.
Surely, this is a bug no?