In the Event log on the server that generates your OAB you may see the following:

Event Type: Error
Event Source: MSExchangeSA
Event Category: OAL Generator
Event ID: 9325
Description:
OALGen will skip user entry 'Display Name' in address list '\Global Address
List' because the SMTP address '' is invalid.
- Default Offline Address List

If you check the user that is mentioned in the event you may find that all of the SMTP proxy addresses look fine on the "E-mail Addresses" tab in Active Directory Users and Computers (ADU&C).  However if you look at the "E-mail" field on the "General" tab you may notice that the address there doesn't match the Primary SMTP address on the "E-mail Addresses" tab (the one next to the bold SMTP).  These have to match.

About the only place I have found this documented is in the link in the actual event.  You know the one that says:

For more information, see Help and Support at:
http://go.microsoft.com/fwlink/events.asp

That link will take you to here, where it says:

"This Error event indicates that the user account specified in the event description has not been included in an offline address list because of an incorrectly configured SMTP address. For example, an incorrectly configured SMTP address is an address that contains a dash "-", an underscore "_", or no characters after the @ symbol. Incorrectly configured SMTP addresses can occur in the following circumstances:

  • A script modified either a user's primary SMTP proxy address attribute or e-mail address attribute. These attributes must match for a user to be added to an offline address list.

  • An administrator modified the e-mail address of a user on a computer that did not have the Exadmin.dll extensions loaded. "

If you have administrators using ADU&C but don't have the Exchange extensions loaded, then they may think that this is the right place to change someone's email address.  If they had the proper extensions this would also change the Primary SMTP address as well, but since they don't...  The next time the server generates the OAB, it will skip this user and your users with Outlook 2003 in cached mode may be missing that mailbox.

I'd be remiss if I didn't mention that OABInteg also helps you with this issue.  See Dave Goldman's blog for more about that.