Windows – Event ID 9331 MSExchangeSA & Event ID 9335 MSExchangeSA

I get this two Exchange 2010 Global Address book related event IDs:

Event ID 9331 MSExchangeSA

OABGen encountered error 80004005 (internal ID 50101f1) accessing the
public folder database while generating the offline address list for
address list '/'.

-\Default Offline Address List

and

Event ID 9335 MSExchangeSA

OABGen encountered error 80004005 while cleaning the offline address
list public folders under /o=xxxxx
xxxx/cn=addrlists/cn=oabs/cn=Default Offline Address List. Please
make sure the public folder database 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.

-\Default Offline Address List

It is Exchange 2010 SP2 sitting on Windows 2008 enterprise edition.

Essentially the issue is that the global address book is not being updated on Outlook clients. We are using Outlook 2007 and 2010.

So far I have tried running the following command:

Update-FileDistributionService -Identity ExchangeServer -Type "OAB"

And I tried this solution as well:

1) Make sure the Microsoft Exchange System Attendant is running. It
will be set to start automatically by default, but it doesn't. This is
a known issue. Start this service manually. When running, you will not
get an error when trying to update the GAL.

2) "Apply" any changes made to any address lists before the GAL will
update Outlook properly. In Organization Configuration -> Mailbox in
EMC, view the properties of the Default Global Address Book in the
Offline Address Book tab. In the properties window, select the Address
Lists tab. This shows which address lists makes up the GAL.

3) Close the properties window and select the Address Lists tab in the
Organization Configuration -> Mailbox. Right-click each address list
used by the Def GAL and click "Apply" (make sure the "Immediately"
radio button is checked).

4) Last, go back to the Offline Address Book tab, right-click the GAL
and select "Update".

After a few send/receives in the Outlook clients, their Glogal Address
List should update to show the latest changes.

Neither one of those solutions helped. So I am not really sure what to do here. Also, I am aware of changing registry on each local computers, but it would be close to impossible as we have 8 offices in 3 different countries.

Any suggestions?

EDIT 7.XII.2012 @ 10.35

I forgot to mention that we did rebuild the address book and that didn't help.

EDIT 27.III.2013 @ 17.15

Well, after running

Get-PublicFolder "\non_ipm_subtree\offline address
book/o=ORG/cn=addrlists/cn=oabs/cn=Default Offline Address list"
-Recurse | Set-PublicFolder -Replicas "second storage group\public folder database"

I get the following error:

When I execute Get-PublicFolder, all I get is IPM_SUBTREE. I tried substituting the non_ipm_subtree with ipm_subtree to no luck…

Still need help! Thanks!