A customer had the issue, that two clients with Outlook 2007 could not access the Availability Services and Automatic Replies. This was happening in the internal network and all other users were not affected. EWS and Autodisocver was working properly.
An Autodiscover test on these clients showed up, that these clients couldn’t find the Autodiscover Service Connection Point (SCP) which is located in Active Directory.

After some analysis and troubleshooting I found that on these Clients for some reasons the following Registry Keys have been in place:

[HKEY_CURRENT_USER\Software\Microsoft\Office\12.0\Outlook\AutoDiscover]
"PreferLocalXML"=dword:00000001
"ExcludeHttpRedirect"=dword:00000001
"ExcludeHttpsAutodiscoverDomain"=dword:00000000
"ExcludeHttpsRootDomain"=dword:00000000
"ExcludeScpLookup"=dword:00000000
"ExcludeSrvLookup"=dword:00000000
"ExcludeSrvRecord"=dword:00000000

After deleting these Registry Keys, Autodiscover was working fine again.