So where do you start looking when Outlook Anywhere HAS been working fine now stops? I had this case today on a Exchange 2007 server with Sp1 and Rollup 2 deployed. The remote outlook clients were receiving mail, but calendaring and GAL lookups failed. Turned out that the RPCPROXY key was mangled. Thanks to Riccardo Moretti for pointing me in the right direction.

The exact key location is HKLM\Software\Microsoft\Rpc\RpcProxy - ValidPorts

The value of ValidPorts had changed to an unexpected one. Trying to understand why I found some interesting articles here:

How does Outlook Anywhere work (and not work)-

http://support.microsoft.com/kb/831051

Ultimately I fixed this by disabling Outlook Anywhere, Reinstalling RPC over HTTP, re-enabling Outlook Anywhere.

After that I monitored the ValidPorts key to make sure it was populated properly and restarted Exchange Services after ensuring the RIGHT values had populated.

I'll try figure out why the key value changed in the first place and update when I know.