We are still running Lync 2010 server and client, so I’m not sure if this is an issue in later versions (or Skype For Business now) – but this problem still occurs in the most patched versions of Lync 2010.

The error “Lync is Experiencing Connection Issues with the Exchange Server” can be caused by many things. The Bytemedev wesbsite lists a lot of common client corruption type solutions to get around the problem.

Checking Lync client logs didn’t help much, and Lync connectivity in Configuration Information just showed an issue in connecting to EWS without any helpful details.

For my case (which has come up more than once), those fixes weren’t the issue. Another blog post got me onto the right track from NetworkAdminSecrets around having a corrupted contact. Lync will fail if it doesn’t like all the contacts in someone’s Contacts – and this includes the Suggested Contacts!

Above is the bad contact I found. Often it won’t like an Asian or European character, but this time it was a space (or some other symbol that’s just being represented by a space). It wasn’t even the saved address, it was the display name. This single record caused the problem.

The painful method I used to find the record was first to scroll through the entire list, looking for a weird character. Since I couldn’t find one, I then moved half of the contacts out, and seeing if the Lync client still complained after a logout/login. Repeating this processed kept narrowing down the contacts until I was left with a few, and could find what I was looking for.

Deleting or fixing the contact was all that was needed to resolve the issue!