We had it working and since the April updates it seems to have stopped. This is on all Lync clients, not just one or two.
I have tried the May Cumalitive update and that has made no difference.
Our issue seems similar to this KB article http://support.microsoft.com/kb/2517721 as all our users do have capitals in their smtp addresses but having already installed the update I am not sure what to do next and I'm very puzzled as to why it would stop working when all looked so good.
We have made no changes to policies so I'm confident that isn't the problem (unless the updates somehow messed with them). No changes to the windows firewall either on the clients so I'm guessing that isn't it either.
Autodiscover works fine and I set up some Exchange Activesync devices today so I'm pretty sure that part is working.
Any tips on what to try next would be much appreciated.