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:

KB 926209 - Error message when Outlook clients synchronize an offline address book with Exchange 2000: "'Microsoft Exchange Server' reported error (0x8004010F)"
http://support.microsoft.com/?kbid=926209

KB 905813 - You receive an error message when you try to synchronize the offline address list on an Exchange Server 2007 or Exchange Server 2003 server while you are using Outlook 2003: "0x8004010F"
http://support.microsoft.com/?kbid=905813

KB 939765 - Error message when Outlook synchronizes an offline address book with Exchange 2007: "0x8004010F"
http://support.microsoft.com/?kbid=939765