due lack of feedback from the previous posters I am unaware if any of these has contacted their Polycom Reseller and/or Polycom Support.
The correct way forward should be to work via your Polycom Reseller and/or Polycom Support in order to troubleshoot this further.
Polycom Global Services
We have been facing the same problem for more than half a year now, and a case was also opened last Novemeber.
Some interesting things I noticed: The very same HDXs worked well with OCS before, but not with Lync. We had less than 200 users. Now after merging with an other company, we have a completely new deployment of Lync, but the problem is the same.
I've also noticed that after rebooting HDX the Lync address book was working for few minutes.
Let's hope that it will be fixed soon.
To close the loop on this thread, this issue was addressed in the 3.0.5 firmware release last month.