Recently, I bumped into Jaap Wesselius’ article about an issue he encountered about Hybrid Free/Busy lookups failing. As this relates to Hybrid Exchange, I was – of course – intrigued and remembered that I (once) encountered a similar scenario, but could not remember how I resolved the problem back then.
After some digging, I came across the following KB article which describes the behavior of Free/Busy requests and why they might fail of Outlook Anywhere is disabled (blocked) on the user-level: http://support2.microsoft.com/kb/2734791/en-us?sd=rss&spid=13159
To make a long story short, if Outlook Anywhere is disabled at the user level, Autodiscover does not return the External EWS URL which is required to make the Free/Busy call.
The solution is as simple as the problem itself: re-enable Outlook Anywhere for the user and you would be fine. Of course, this might – depending on your environment – be a little challenging. This being said, however, I do suggest that you configure and (if possible) use Outlook Anywhere as it will make your life easier down the road (e.g. for migrations to Exchange 2013).
This statement “To make a long story short, if Outlook Anywhere is disabled at the user level, Autodiscover does not return the External EWS URL which is required to make the Free/Busy call.” is completely false and you should not mix up EWS with OutlookAnywhere, they are 2 different virtual directories on the Exchange CAS servers and have no bearing on each other for Free/Busy. The only requirements for Free/Busy to work are proper autodiscover externally and EWS externally.
I would suggest that you read the KB article, and then rethink your statement. I am not saying that the OutlookAnywhere URL is the same as EWS. Just saying that AutoD doesn’t hand out the latter when the former functionality is disabled on the user level.