I have run into this problem with an Exchange Server 2007 SP1 implementation running on Windows Server 2008 x64. I also noticed some forum posts where people had the exact same issue on Windows Server 2003 x64, however I cannot verify the solution method described here would help if you're on Windows Server 2003 x64.
Although the main problem is with the Autodiscover web service, you may experience crashes in Outlook 2007 with Scheduling Assistant or errors with Out of Office Asisstant (OOF). Also Offline Addressbook (OAB) downloads may not work properly. When used with Outlook 2007, all these features depend on Autodiscover, so they fail when Autodiscover has a problem. In my case, users noticed that they were not able to "Add Attendees" when trying to create a meeting request with Scheduling Assistant. Outlook 2007 was crashing when they selected an attendee from the addressbook. After a brief research, I also noticed that Out of Office Assitant was also failing with "Your Out of Office settings cannot be displayed, because the server is currently unavailable" message. My attempts to download Offline Address Book were also unsuccessful. Download attempts did not succeed, but they ran forever and did not produce an error message either.
I will not list all the boring troubleshooting details here, but I want to mention that I deleted and recreated Autodiscover virtual directory with "Remove-AutodiscoverVirtualDirectory" and "New-AutodiscoverVirtualDirectory" commandlets in Powershell. These commands ran without any issues, but they did not help.
Also I ran "Test-OutlookWebServices" commandlet on Exchange Server and received the following error at the fourth step:
PS] C:\Windows\System32>Test-OutlookWebServices |fl
Id : 1003
Type : Information
Message : About to test AutoDiscover with the e-mail address Administrator@xyz.com.
Id : 1007
Type : Information
Message : Testing server EX01.xyz.com with the published name https://EX01.xyz.com/EWS/Exchange.asmx & https://mail.xyz.com/EWS/Exchange.asmx.
Id : 1019
Type : Information
Message : Found a valid AutoDiscover service connection point. The AutoDiscover URL on this object is https://EX01.xyz.com/autodiscover/autodiscover.xml.
Id : 1006
Type : Information
Message : The Autodiscover service was contacted at https://EX01.xyz.com/autodiscover/autodiscover.xml.
WARNING: An unexpected error has occurred and debug information is being generated: Object reference not set to an instance of an object.
Test-OutlookWebServices : Object reference not set to an instance of an object.
At line:1 char:24
+ Test-OutlookWebServices <<<< |fl
Because Outlook "Test E-mail AutoConfiguration" ended with a "certificate error" I also re-created the SSL certificate and enabled it for all services. No need to say, none of these actions resolved the problem.
I was able to find the actual problem source and solution at Technet Forums. (At http://forums.microsoft.com/TechNet/ShowPost.aspx?PageIndex=0&SiteID=17&PageID=0&PostID=3760137, to be exact.) Apparently, the problem was caused by a bug in ".NET Framework 2.0 SP2". It simply was not playing nicely with Exchange Server 2007 SP1. Even though you don't explicitly select to install this .NET 2.0 Service Pack 2, it is installed as a part of ".NET Framework 3.5 SP1" setup. With this information, I searched for .NET Framework 2.0 SP2 in Programs and Features, but failed to find it. So I uninstalled .NET Framework 3.5 SP1 instead and restarted the server. However this did not help. Finally, I found that the .NET 2.0 SP2 was displayed as "Update for Microsoft Windows (KB948609)" in Windows 2008 Programs and Features. After I had uninstalled this update, all of my problems disapperared. I was able to verify that Out of Office Assistant, Scheduling Assistant and Offline Address Book downloads were fully functional. In addition, all error messages disappeared from "Test-OutlookWebServices" test in Powershell and "Test E-mail AutoConfiguration" test in Outlook.
I had to spend long hours searching the web and testing every possible solution to find the actual one. Hope this post will reduce your troubleshooting period. Please use the Comments link below if want to say something about this post.