We have an Exchange 2007 environment.
Everything is running fine, however last week we created a new mailbox for a user named David Jones. For some reason, this is not appearing in the GAL (clients cannot search for him even in OWA). I checked and the mailbox is not hidden from the GAL or anything like that.
I checked "update address based on email policy" and this was unticked, as it is for all our users.