For companies that have a mixed 2003/2007 environment and fall under one of the following states might see problems when querying legacy Free/Busy information:

1. Companies that are in the middle of a migration.
2. Companies that have already migrated and not realized migration problems such as changed attributes.

Event ID      : 4004
Category     : Availability Service
Source         : MSExchange Availability
Type            : Warning
Generated   : 27.09.2007 08:16:08
Machine       : ExchangeServer01
Message      : Process 2148[w3wp.exe:/LM/W3SVC/1/ROOT/EWS-1-128353572646987287]: Unable to find a public folder server for organizational unit (OU) CompanyUsers. The service will attempt to find a random server, which may take a longer time to service the request.

Looking deeper in to this event we can see the following:

<data name="PublicFolderServerNotFoundForOU">
<stringvalue>Process %1: Unable to find a public folder server for organizational unit (OU) %2. The service will attempt to find a random server, which may take a longer time to service the request.</stringvalue>
<eventmessageid>4004</eventmessageid>
<eventtype>Warning</eventtype>
<severity>Error</severity>
<facility>Interface</facility>
<language>English</language>
<category>Availability Service</category>
<level>Lowest</level>
<period>LogPeriodic</period>
<comment>Indicates a failure to find the server to look up free busy information for legacy mailbox(es).</comment>
</data>

Currently there are a few causes for this (More to be added later):

1. After the migration of the user the legacyExchangeDN still points to the decommissioned AG and that server no longer exists.
2. There are multiple servers and only one replica of the Free/Busy information.

Here is a high level overview on what happens when an Outlook client makes a Free/Busy request:

1. The Outlook 2007 client communicates with the Availability service for a Free/Busy request.
2. We will see if this is an Exchange 2007 mailbox and if it is the availability service will communicate directly with the users mailbox. If this is a legacy user we need to look up the user in the active directory so we can see what public folder store he has his data on.
3. The Availability service makes a query for that users legacyExchangeDN and homeServer attribute.
4. At this point we will make a connection to that server for the user in question.
5. Lookup the public folder server for this organizational unit - (Admin Group).
6. Look in our cache and report how many server objects we have that can be used.
7. Pick a random server from the list.
8. Check to see if we can communicate with this server. If we can not this server then gets added to the badServers list.
9. Make another query for another server.
10. At this point we will look for any server from any organizational unit - (Admin Group). Since this server might not contain the data that we are looking for add them to the badServers list as well.
11. As a last resort we look through the entire list and pick any server we can and then clear the badServers list.

Reason servers get added to the badServers list
If for any reason you have any connection issues or we can not find what we are looking for at the time of the query we will add the server to the bad list. Once this happens the server will stay inthe list unntil you restart the MSExchangeServicesAppPool, recycle the services or a successful query is made.

How to fix

Item #1
The problem here is that the legacyExchangeDN for the user is invalid. In order for the Availability service to work it needs to the correct legacyExchangeDN for the user so it can look up that users homeServer and then from there get the list of public folders. If we bind to an invalid legacyExchangeDN the domain controller we are querying will throw an DS_NO_SUCH_OBJECT error which gets returned back to exchange and then the query fails. Once the legacyExchangeDN is corrected this problem should go away.

Item #2
The fix is for you to put Free/Busy replica's on each of your servers in that administrative group. This is not an optimal fix but is required to fix this problem. Currently this is by design and there is no way to force the availability service to pickup Free/Busy data from a specific PF server.