An issue with address book in Exchange 2013. It was showing error "Outlook 2013 Exchange 2013 Address Book Error 0x8004010F : The operation failed. An object cannot be found" 

Some info about OAB in Exchange 2013

As there is a change in Exchange 2013, Address book distribution and offline address is stored in organization mailbox (As per the article from Exchange Team).

CAS server proxy the request to nearest/available database mounted mailbox server which contains system/Arbitration mailbox.

Steps to troubleshoot:

1. Make sure Autodiscover is correct.

Get-clientAccessServer | fl Name,AutoDiscoverServiceInternalUri

 If not correct, please change the URL using the below command:

Set-ClientAccessServer -Identity server1 -AutoDiscoverServiceInternalUri ""

2. Check your OAB URLs set properly.

Get-OabVirtualDirectory -server SERVERNAME

Set your URLs if it is not correct.

Set-OabVirtualDirectory -Identity "server1\oab (default web site)" -InternalUrl -ExternalUrl

Reset IIS using the command "iisreset /noforce". Then make sure it is correct using "Test E-mail AutoConfiguration". Example here. It would be similar to this:

3. OAB

Make sure OAB is tagged in all the databases using the below command.

Get-MailboxDatabase | Ft Name, *book*

If you see any database not tagged, tag the OAB to the database using the below command:

Get-Mailboxdatabase | Set-MailboxDatabase -OfflineAddressBook “Default Offline Address Book”

4. Make sure System/Arbitration mailbox exists.

It should be similar to the below screenshot:

Get-Mailbox -Arbitration | where {$_.PersistedCapabilities -like “*OAB*”} | ft Name, Servername, Database

 If it is missing you could create a new one and tag the databases using the below commands:

New-OfflineAddressBook -Name “NewOfflineAddressBook” -AddressLists “\Default Global Address List” -VirtualDirectories “SERVERNAME\OAB (Default Web Site)”

5.Tag the new OAB to the databases.

Get-Mailboxdatabase | Set-MailboxDatabase -OfflineAddressBook “NewOfflineAddressBook”

Restart the MS Exchange File distribution service and MS Exchange System attendant service. If restarting the services does not help, please try restarting the servers as well as in some cases the restart helped. 

See Example