I just recently migrated all of our users from Exchange 2010 > Exchange 2013 CU9. Our 2010 environment was in horrible condition.  Certs were wrong, configuration was wrong, everthing was wrong.  Our 2010 servers are EXCHANGE-0x and our 2013 servers are the EX13 servers.  We have multiple users, not all, that have users completely missing in the GAL. When trying to manually update the address book, we get the following message:

Task 'testu@wsecu.org' reported error (0x8004010F) : 'The operation failed.  An object cannot be found.'.
I have found multiple articles on this issue and nothing seems to fix what I am experiencing.  Here are all of the commands that I have run:

[PS] C:\>Get-OabVirtualDirectory -ADPropertiesOnly | ft Identity, *Auth* -AutoSize

Identity    BasicAuthentication WindowsAuthentication OAuthAuthentication InternalAuthenticationMethods
--------    ------------------- --------------------- ------------------- ------------------
EXCHANGE-02\OAB (Default Web Site) False   False   False   {WindowsIntegra...
EXCHANGE-01\OAB (Default Web Site)  False   False   False   {WindowsIntegra...
EX13CAS-01\OAB (Default Web Site) False   False   False   {WindowsIntegra...
EX13CAS-01\OAB (Default Web Site) False   False   False   {WindowsIntegra...

[PS] C:\>Get-OabVirtualDirectory -ADPropertiesOnly | ft Identity, *url* -AutoSize Identity    InternalUrl    ExternalUrl
--------    -----------    -----------
EXCHANGE-02\OAB (Default Web Site) http://exchange-02.domain.int/OAB https://cert.domain.org/OAB
EXCHANGE-01\OAB (Default Web Site) https://cert.domain.org/oab  https://cert.domain.org/OAB
EX13CAS-01\OAB (Default Web Site) https://outlook.domain.net/OAB  https://outlook.domain.net/OAB
EX13CAS-01\OAB (Default Web Site) https://outlook.domain.net/OAB  https://outlook.domain.net/OAB
 [PS] C:\>Get-Mailbox -Arbitration | where {$_.PersistedCapabilities -like "*OAB*"} | ft Name, Servername, Database -AutoSize Name       ServerName Database
----       ---------- --------
SystemMailbox{bb558c35-97f1-4cb9-8ff7-d53741dc928c} ex13mbx-01 Information Technology
[PS] C:\>Get-MailboxDatabase | Ft Name, *book* Name   OfflineAddressBook
----   ------------------
Information Technology \Default Offline Address List (Ex2013)
OWF Journaling  \Default Offline Address List (Ex2013)
Back Office  \Default Offline Address List (Ex2013)
Front Office  \Default Offline Address List (Ex2013)
Management  \Default Offline Address List (Ex2013)
Marketing  \Default Offline Address List (Ex2013)
TempDB   \Default Offline Address List (Ex2013)
General   \Default Offline Address List (Ex2013)
Resources  \Default Offline Address List (Ex2013)

[PS] C:\>Get-Mailbox TestU | fl Name, OfflineAddressBook,Database

Name      : test user
OfflineAddressBook:
Database     : Information Technology

As you can see I have assigned the offline address book to all mailbox databases, yet when I do a lookup on an individual user, it shoes that no offlineaddressbook has been configured.

Any help would be greatly appreciated.

What about Get-OfflineAddressBook | FL?

Please check the below link to trouble shoot the Address book issue.

http://msexchangeguru.com/2013/12/04/e2013-oab/

Also check the current Exchange 2013 Mailbox server is generating the address book or not.

check the below path and its having the latest .xml file of OAB.

C:\Program Files\Microsoft\Exchange Server\V15\ClientAccess\502e9804-93ae-057aafb60291\OAB.xml

Did you try to create another offline address book and check.

[PS] C:\>Get-OfflineAddressBook | FL

RunspaceId                       : 096a34ca-e112-4df0-b826-ecd197ec694f
Server                           : EXCHANGE-01
GeneratingMailbox                :
AddressLists                     : {\Default Global Address List}
Versions                         : {Version2, Version3, Version4}
IsDefault                        : False
PublicFolderDatabase             : Public Folder Database [EXCHANGE-01]
PublicFolderDistributionEnabled  : True
GlobalWebDistributionEnabled     : False
WebDistributionEnabled           : False
ShadowMailboxDistributionEnabled : False
LastTouchedTime                  :
LastRequestedTime                :
LastFailedTime                   :
LastNumberOfRecords              :
LastGeneratingData               :
MaxBinaryPropertySize            : 32768
MaxMultivaluedBinaryPropertySize : 65536
MaxStringPropertySize            : 3400
MaxMultivaluedStringPropertySize : 65536
ConfiguredAttributes             : {}
DiffRetentionPeriod              :
Schedule                         : {Sun.1:00 AM-Sun.2:00 AM, Sun.5:00 AM-Sun.6:00 AM, Sun.9:00 AM-Sun.10:00 AM,
                                   Sun.1:00 PM-Sun.2:00 PM, Sun.5:00 PM-Sun.6:00 PM, Sun.9:00 PM-Sun.10:00 PM,
                                   Mon.1:00 AM-Mon.2:00 AM, Mon.5:00 AM-Mon.6:00 AM, Mon.9:00 AM-Mon.10:00 AM,
                                   Mon.1:00 PM-Mon.2:00 PM, Mon.5:00 PM-Mon.6:00 PM, Mon.9:00 PM-Mon.10:00 PM,
                                   Tue.1:00 AM-Tue.2:00 AM, Tue.5:00 AM-Tue.6:00 AM, Tue.9:00 AM-Tue.10:00 AM,
                                   Tue.1:00 PM-Tue.2:00 PM...}
VirtualDirectories               : {}
AdminDisplayName                 :
Identity                         : \Default Offline Address List
IsValid                          : True
ExchangeVersion                  : 0.0 (6.5.6500.0)
Name                             : Default Offline Address List
DistinguishedName                : CN=Default Offline Address List,CN=Offline Address Lists,CN=Address Lists
                                   Container,CN=State CU,CN=Microsoft
                                   Exchange,CN=Services,CN=Configuration,DC=domain,DC=int
Guid                             : 5e937ec9-2ffb-4d93-95be-a736620e3b88
ObjectCategory                   : domain.int/Configuration/Schema/ms-Exch-OAB
ObjectClass                      : {top, msExchOAB}
WhenChanged                      : 8/5/2015 6:13:37 AM
WhenCreated                      : 7/25/2003 3:59:07 PM
WhenChangedUTC                   : 8/5/2015 1:13:37 PM
WhenCreatedUTC                   : 7/25/2003 10:59:07 PM
OrganizationId                   :
Id                               : \Default Offline Address List
OriginatingServer                : AD-01.domain.int
ObjectState                      : Unchanged

RunspaceId                       : 096a34ca-e112-4df0-b826-ecd197ec694f
Server                           :
GeneratingMailbox                : domain.int/Users/SystemMailbox{bb558c35-97f1-4cb9-8ff7-d53741dc928c}
AddressLists                     : {\Default Global Address List}
Versions                         : {Version4}
IsDefault                        : True
PublicFolderDatabase             :
PublicFolderDistributionEnabled  : False
GlobalWebDistributionEnabled     : False
WebDistributionEnabled           : False
ShadowMailboxDistributionEnabled : False
LastTouchedTime                  :
LastRequestedTime                :
LastFailedTime                   :
LastNumberOfRecords              :
LastGeneratingData               :
MaxBinaryPropertySize            : 32768
MaxMultivaluedBinaryPropertySize : 65536
MaxStringPropertySize            : 3400
MaxMultivaluedStringPropertySize : 65536
ConfiguredAttributes             : {OfficeLocation, ANR, ProxyAddresses, ANR, PhoneticGivenName, ANR, GivenName, ANR,
                                   PhoneticSurname, ANR, Surname, ANR, Account, ANR, PhoneticDisplayName, ANR,
                                   UserInformationDisplayName, ANR, IsOrganizational, Value, ExternalMemberCount,
                                   Value, TotalMemberCount, Value, ModerationEnabled, Value, DelivContLength, Value,
                                   MailTipTranslations, Value, ObjectGuid, Value...}
DiffRetentionPeriod              : 30
Schedule                         : {Sun.5:00 AM-Sun.5:15 AM, Mon.5:00 AM-Mon.5:15 AM, Tue.5:00 AM-Tue.5:15 AM,
                                   Wed.5:00 AM-Wed.5:15 AM, Thu.5:00 AM-Thu.5:15 AM, Fri.5:00 AM-Fri.5:15 AM, Sat.5:00
                                   AM-Sat.5:15 AM}
VirtualDirectories               : {}
AdminDisplayName                 :
Identity                         : \Default Offline Address List (Ex2013)
IsValid                          : True
ExchangeVersion                  : 0.20 (15.0.0.0)
Name                             : Default Offline Address List (Ex2013)
DistinguishedName                : CN=Default Offline Address List (Ex2013),CN=Offline Address Lists,CN=Address Lists
                                   Container,CN=Washington State CU,CN=Microsoft
                                   Exchange,CN=Services,CN=Configuration,DC=domain,DC=int
Guid                             : 34115ca3-73b5-4d64-88d6-18b82c5e9233
ObjectCategory                   : domain.int/Configuration/Schema/ms-Exch-OAB
ObjectClass                      : {top, msExchOAB}
WhenChanged                      : 7/7/2015 10:29:04 PM
WhenCreated                      : 4/28/2015 9:57:59 AM
WhenChangedUTC                   : 7/8/2015 5:29:04 AM
WhenCreatedUTC                   : 4/28/2015 4:57:59 PM
OrganizationId                   :
Id                               : \Default Offline Address List (Ex2013)
OriginatingServer                : AD-01.domain.int
ObjectState                      : Unchanged

Looks like web distribution isn't enabled "WebDistributionEnabled           : False"

The Default Offline address book is assigned through the mailbox database.  Check the "Client Settings" section on the mailbox database in the EAC.

If you have different address books that need to be assigned to different users, then you might want to look at address book policies.

Have you verified through OWA that the affected users have the correct users showing up in their address book there?

That might be the best idea.  Create a new OAB, assign it as the OAB for all your mailbox databases, and then remove the old OABs.

You have two OABs there.  Make sure the right one is assigned to the databases, and delete the other one.  Or follow the other advice below and create a new one entirely.