Post reboot of an Exchange public folder & mailbox server, this error was received by Outlook 2003 clients. Outlook 2007 clients had no problems. Reason is because the public folder database was offline, i.e. failed to mount. The following services had failed to start: Information Store, System Attendant and Service Host.

After restarting these services successfully, the Information Store was able to mount the PF database and the error is cleared for the clients. The PF database stored the offline address book for these clients and that was the object that could not be found.

This MS KB article, covers a different reason that the same error might be seen client side – because the selected OAB for the mailbox database the client was located on had an invalid (old, deleted, ???) offline address book configured.

Also, the reason that the services originally failed to start appears to be because the IS service was unable to contact an Active Directory domain controller when starting up:

Event Type: Error
Event Source: MSExchangeIS
Event Category: General
Event ID: 1121
Date: 10/8/2009
Time: 12:00:46 PM
User: N/A
Computer: PAC-MSG-HTR1
Description:
Error 0x96f connecting to the Microsoft Active Directory.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

Possibly an idea to set the recovery action of these services to restart in X minutes time, especially if the site is recovering from a power outage or some other reason that both the Exchange servers and AD servers would be down or restart at the same time.

Finally, this link [msexchangeteam.com] has lots of good information on the various possible scenarios resulting in an 0x800401oF MAPI error

Popularity: 30% [?]