So, recently we worked an issue for a customer that we struggled with for a long time: Exchange 2003 users couldn't see Free/Busy information for users who had been moved to Office365. This should work and is fully supported as part of Office365 migration and coexistence.
Exchange 2003 relies upon Free/Busy in Public Folders. So, when an Exchange 2003 user goes to get Free/Busy information for someone else, the client goes to the corresponding Public Folder where the target user's client has published their availability.
In Exchange 2007 we began moving away from using Public Folders for Free/Busy by introducing the Availability Service, which Exchange 2010 (and Office365) also uses. Both Exchange 2007 and Exchange 2010 can use Public Folders for free/busy as well, but the preference is to use the availability service. Office365 solely uses the Availability Service as there's no Public Folders with Office365.
How's it supposed to work?
So, how does an Exchange 2003 user get Free/Busy information for a cloud user? What happens is that when you setup coexistence with the cloud, the cloud user's Free/Busy points to the on-premise Exchange 2010 (usually the coexistence server by default). When a client on Exchange 2003 queries for Free/Busy for a cloud user, the Exchange 2003 server believes that the Public Folder store on Exchange 2010 has a copy and therefore redirects the client to the Exchange 2010 server. The Exchange 2010 server intercepts this public folder request and makes the request out to the cloud's availability service, gets the information, and then passes it back to the client. As far as the client knows, it got the information from a Free/Busy Public Folder.
However, with this customer, the requests were never making it to the Exchange 2010 server. This is what we struggled with...and finally stumbled across what was going on.
For more information on how Cross Org Availability works (which includes Office365) see the Exchange Team's blog entry on the subject.
The customer in question was using a feature of Exchange 2003 called Public Folder Referral Order (PFRO). This feature allows admins to control which public folder servers are used via setting a priority order. By default, Exchange 2003 wants to use the Routing Group connector costs to determine where to refer a client to if the default PF store you connect to doesn't have a copy of the public folder you want. But, if the cost between two RGs in the US have the same cost as say the RGC to an Asia location, then there's a chance a client will be sent to Asia instead of the US server! The Public Folder Referral Order feature allows you to override this and prioritize the 2nd US server over the Asia server for a US server and so on. This was a fairly popular feature when it was released, but with so many migrations off Exchange 2003 and consolidations done by companies, it's not used much anymore and therefore was not tested with Office365 coexistence.
By turning off Public Folder Referral Order, Exchange 2003 users were properly redirected to the Exchange 2010 server...once PFRO was re-enabled, it stopped working.
Digging into the traces, we found that when you add the Exchange 2010 servers to the PFRO list (which is needed to be done), it doesn't add the server...it adds the actual PF store name (actually we store the GUID). Problem with that is Exchange 2003 needs to know the server to redirect the request to, and doesn't know how to resolve that from the PF DB value. This happens because Exchange 2010 is database-centric, where previous versions of Exchange were server-centric. In order to resolve this, we had to go into AD via ADSIEdit and replace the DB GUID with the Exchange 2010 server GUID in the msExchDelegateListLink attribute.
There are plans to write a KB article on this issue, but it's not yet available (I'll update this article with the link to it once it does get published).
Thanks to Dan Rowley and Austin McCollum for their help in getting to the bottom of this issue.