When setting up Outlook in cached mode, a common “Synchronization Failed” error is 0x8004010f – which means “address list not found” (the technical description of this is MAPI_E_NOTFOUND). There are three very common issues that may cause this:
1] You haven’t waited long enough! Unless you manually download a pre-created address book, it can take up to 48 hours for Outlook to download a new address book.
2] Your Exchange administrator forgot to specify a Default Offline Address List when he created your message store. In Exchange 2003, in the Exchange System Manager, this setting is on the General tab for the mailbox store. In Exchange 2007, in the Exchange Management Console, this setting is on the Client Settings tab for the mailbox store.
3] Your Exchange administrator has either removed the Default Offline Address List or has been messing with the security on it. Both are much more difficult to correct! You might want to encourage a call to Customer Support Services to get this one fixed.
Thankfully, the most common issues are the first two.
For more information, see these articles in the Microsoft Knowledge Base: