There are two options for resolving a client-side issue with the offline address book
1) Toggle off cached exchange mode and then re-enable it after a sync is complete
2) Force a re-download of the offline address book.
Unless the sync errors for the clients are showing inability to update the offline address book, those are the two items that need to be addressed.
As a gut check anytime someone is curious if someone should be in the GAL, this is what you should check
1) is the person hidden from whitepages – if they are then they should be hidden in the GAL
2) is the person showing up in a normal OWA search. if they are, then it is a problem with the local mail client and not the global address book.