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).