This should be a server-level setting. Your Exchange admin should be able to configure the time interval between updates for your Offline address book downloads. It's possible that you're looking for the new users before your interval period has expired. To additionally complicate things, the OAB on the server is by default generated once per day, at midnight. Depending on the size of your organization and changes to default settings, it could take days before a new user can make its way into the OAB and onto your local copy.
It's also possible that there's an issue with client-server communication such that OAB downloads aren't happening.
If you go to Tools --> Send/Receive --> Download Address Book, does it successfully update? That will rule out a communications issue in receiving differential OAB updates.
MSKB 841273 is pretty exhaustive. There's a lot of server-side info there that won't help you, but there are some client-side settings you can change to monitor & adjust Outlook's OAB-fetching behavior.