I am running Exchange 2007 and the clients are all Outlook 2007.
I have a new user that does not appear in the GAL but does appear in the address book - All Users.
New user appears in GAL when client not running in cached mode and also when OAB files are removed. User appears in OWA.
Ran the command get-offlineaddressbook | update-offlineaddressbook and waited a day and redownloaded (Full) address book to no avail.
Created a new OAB, set as Default waited and repeated above to no avail.