I had a user with Outlook 2011 for Mac (running on OS X 10.8) connected to his Exchange account. The server runs SBS 2008, fully patched (running Exchange 2007 SP 3).
The Outlook account was set up using autodiscover when the user was on the same LAN as the Exchange server. When the user was not on the same LAN as the Exchange server, autocomplete did not work.
I troubleshot this problem off-site where I was able to replicate the problem.
I'm not sure exactly what I did to fix the problem, but I'm going to document what I did and what I saw.
First, I investigated the user's settings. Interestingly, the field for server under directory services was blank. I wasn't sure if there was supposed to be something there. I assumed yes.
I created a new identity in Outlook 2011 and created a new Exchange account in that new identity that pointed to my personal Office365 account. I let autodiscover create the Outlook connection settings. Interestingly, there was nothing there in the server field for directory services either. The autocomplete was not working in this Outlook profile/account either.
I logged out as the user and logged in as another user (another local account on the Mac). I opened Outlook and Office update told me there was an update to install (perhaps 10.2.5 - I'm not sure). I let that update install. I opened Outlook and set up an Exchange account for a complete separate client that also has an SBS 2008 server (fully patched). I let autodiscover create the settings. Autocomplete was not working on this account either, but I did notice that there was a value in the server field in directory services. The value was set to servername.domainname.local. Clearly, this server would not resolve since the server was not local and there was no route to the server. This make some logical sense to me that my client's autocomplete was working in the office when he was on the same LAN as the server so Outlook must have been able to route to the server in some way to pull autocomplete data. So I replaced servername.domainname.local with the FQDN of the server - remote.contoso.com. I checked the box for SSL. Directory services said it would use port 3269 so I went to the firewall of my SBS 2008 server and redirected port 3269 to the local IP of my SBS 2008 box. I closed Outlook and reopened it. Outlook complained of a certificate mismatch (directory services was pointing to remote.contoso.com but the cert was for servername.domainname.local). I allowed Outlook to use the server anyway despite the certificate mismatch. And lo and behold, autocomplete began working.
In addition, Office 2011 also notified me of another update, 10.2.6 i believe - which I allowed to install.
But this is where it gets weird.
I go back into my the user's original profile and autocomplete is working. I made no changes to his Exchange account. None at all. All I did was get aucomplete working on another Exchange account in a completely different Mac profile. There is no reason that would have any effect on the user's profile. Autocomplete also began working on my Office365 profile as well.
I rebooted the Mac and the changes persisted (autocomplete still working). I disconnected from the WLAN the Mac was on and connected the Mac to my iphone's personal hotspot and the changes persisted (autcomplete still working).
I can't narrow this down to a specific thing I did to fix it, but it's working.