There are several reasons for why an Outlook client can receive the 8004010F error when trying to download the Offline Address Book files from an Exchange Server. Additionally you can end up with some events in the application log when diagnostic logging is turned up for MSExchangeIS\Public Store,

This issue occurs if the OAB system folders are not replicating to any Exchange server. The OAB system folders must replicate to at least one Exchange server. By default, the first Exchange server in the organization contains the OAB system folders replica. However, the OAB system folders may not replicate to any Exchange server if the following conditions are true:

• The first Exchange server in the organization is decommissioned incorrectly. 
• The replica list is blank after the name of this server is removed from the replica list.

Event ID : 3043
Category : Replication Site Folders
Source : MSExchangeIS Public Store
Type : Error
Generated : Date
Written : Time
Machine : Server_Name
Message : Error 0xfffff9bb occurred while performing a site folder check for Public Folder Store "First Storage Group\Public Folder Store (EXCH1)".

Event ID : 3048
Category : Replication Site Folders
Source : MSExchangeIS Public Store
Type : Error
Generated : Date
Written : Time
Machine : Server_Name
Message : Error -1605 occurred while creating site folder (a-8) NON_IPM_SUBTREE\OFFLINE ADDRESS BOOK\/o=Test/cn=addrlists/cn=oabs/cn=TestOAB

Event ID : 9335
Category : OAL Generator
Source : MSExchangeSA
Type : Error
Generated : Date
Written : Time
Machine : Server_Name
Message : OALGen encountered error 80040107 while cleaning the offline address list public folders under /o=Test/cn=addrlists/cn=oabs/cn=TestOAB. Please make sure the public folder store is mounted and replicas exist of the offline address list folders. No offline address lists have been generated. Please check the event log for more information.

Event ID : 9331
Category : OAL Generator
Source : MSExchangeSA
Type : Error
Generated : Date
Written : Time
Machine : Server_Name
Message : OALGen encountered error 80040107(internal ID 50101df) accessing the public folder store while generating the offline address list for address list.

Using err.exe (Microsoft Exchange Server Error Code Look-up Tool) you can  look up both error codes listed in the event id descriptions:

C:\WXP\system32>err 80040107
# for hex 80040107/ decimal -2147221241
ecInvalidEntryId ec.h
MAPI_E_INVALID_ENTRYID mapicode.h
# 2 matches found for "80040107"

NOTE on MAPI Error 80040107: Every folder with in an Exchange database has an EntryID. MAPI clients such as OABgen.dll and Outlook will call OpenEntry() and use the EntryID given to gain access to folders in the Exchange Information Store. In this case the EntryID that is being referenced is to the OAB system folder. This error is returned because the folder in the information store does not exist.

RESOLUTION
To resolve this issue, replicate the OAB system folders to at least one Exchange server. To do this, follow these steps:

1. Click Start, point to All Programs, point to Microsoft Exchange, and then click System Manager.
2. In the administrative group that hosts the folder hierarchies, expand Folders.
3. Right-click Public Folders, and then click View System Folders.
4. Expand Public Folders, and then expand OFFLINE ADDRESS BOOK.
5. Right-click the first subfolder in the Offline Address Book folder, and then click Properties.
6. On the Replication tab, click Add, and then select the Exchange server or the Exchange servers where you want the OAB to be replicated.
7. Click OK two times.
8. Expand the folder to which you just added the replica, and then repeat steps 5 through 7 for each subfolder in that folder.
9. Repeat steps 5 through 8 for each subfolder in the Offline Address Book folder. Alternatively, you can wait for the OAB system folders to automatically propagate the settings to the subfolder's in the Offline Address Book folder.

Dave