It originally started as a minor problem. One of our employees did not get updates for the offline address book (OAB) from the Exchange server. One person was missing from there and it was just one PC that had this issue. Naturally, we tried updating OAB. Got the error 0x8004010F (The operation failed. An object could not be found). Strangely enough, we then tried to update OAB from other PCs and got the same error. However, all those PC had no problem showing that contact on the list.

Internet suggested 0x8004010F being a common problem and proposed tons of things to do. Try googling and see, I bet the links are still there. However, none of those helped. It became obvious I need to apply several fixes in a sequence. Luckily, I found a sequence, which worked for me. But first, some words about our environment.

The Exchange was 2007 SP1, previously upgraded from 2007 and 2003 before that, and our clients were running Outlook 2003/2007 with latest updates. The problem appeared particularly in Outlook 2007 SP2, which did not look like a compatibility issue (especially since we didn't have this elsewhere). Many steps were taken to find what is happening and how to solve it, and I'm not going to waste your time on each. Instead, here is a list, which helped, with some  useful comments:

1. Start EMC (Console), navigate to Organization Configuration/Mailbox/Offline Address Book. You probably have the Default OAB there. See 'Generation Server' field. If it's not your current server, then most likely you have the same problem I did.
   
   
2. Now the goal is to have a default offline address book, with generation server = your current one, mapped to your mailbox database (EMC/Server Configuration/Mailbox/(Right click your database)/Properties/Client Settings/Offline Address Book). If it is already configured this way, you probably need to skip this step. Otherwise, create a new OAB with default settings, set it as default. Make sure you have set compatibility to versions you need, and web access & public folder boxes ticked. Remap your database to the new OAB, remove the old one.
   
   
3. Through EMS (shell) execute the following two commands to recreate virtual directory for OAB distribution:
   
   Remove-OABVirtualDirectory -Identity “SERVER\OAB (Default Web Site)”
New-OABVirtualDirectory
   SERVER is the name of your server. Then you need to enable Web based distribution on your default OAB (tick the box under Distribution).
   Not sure if this step is needed to fix the above problem, but it was part of my solution.
   
   
4. On client PC: restart Outlook, see if the same error persists. If it does, you might need to re-tell outlook to point to the new OAB (Tools ->Send/Receive ->Send/Receive Settings ->Define Send/Receive Groups ->press Edit button ->press Address Book Settings ->click OK twice to get back to Send/Receive Groups window ->press Close button ->Restart outlook, try updating. If you get an error 0x80190194 - a new one, we're almost done)
   
   
5. On the server, open management shell and execute these commands:
   
   net stop MSExchangeFDS
net start MSExchangeFDS
   
   
6. On client PC, restart Outlook and watch how OAB updates perfectly. Or, if you wait until next day, most probably you don't even need to manually update it, as Exchange will handle it.

It was quite a long journey for me to get it right! Hope I didn't miss any steps. And I hope it can help you, the reader. Sorry if I put any optional/unnecessary ones. It doesn't hurt anybody, does it? :)