Problem solved. The issue was that some of the mail clients still had cached recipient information from a previous Exchange installation. To fix this problem:
1.) Delete the Outlook clients nickname cache file by searching the local Outlook profile for a .NK2 file and deleting it.
2.) Change the Outlook to non-cached mode to ensure it is not a cached entry from the Offline Address Book.
3.) Check the behavior in OWA to confirm the server is generating the correct address list and has updated the GAL.