Bit advanced for your average PPRuNe readership !
Disclaimer: I'm no Exchange guru...
What Outlook client version are you using ? 2k3, 2k7,2k10 ?
If 2k3 you might want to try deleting local offline OAB files.
Might also want to consider the steps in this thread :
Outlook 2003 Offline Address book sync failed with error code 0X8004010F Exchange 2007
This might also be of interest :
Earlier Outlook clients cant connect to Exchange 2007 Server
Might also want to look at turning up logging
Something like ......
Set-EventLogLevel "MSExchangeSA\OAL Generator" -Level high
Followed by OAB recreation
Followed by
Get-EventLog Application | Where {$_.Category -eq "OAL Generator"}
Caveat emptor.