In the last few Lync deployments I've done I've run into two different instances where the Lync client was failing to login to Exchange Web Services to retrieve the conversation history and user voicemail. In both cases there wasn't actually the red exclamation mark on those two tabs in the UI like you'd expect if there were an error; the client just hummed along like nothing was wrong. In each scenario if I viewed the configuration information you would see the client report "EWS Not Deployed", which was odd because Exchange 2010 was most definitely deployed at both customer sites.
Sidenote: The EWS polling takes roughly 30 seconds to reach this state. If you view the configuration info immediately you'll see "EWS OK", which is only because Lync has tried yet. So be careful when testing this and thinking everything is just fine.
Solution 1: Verify the InternalURL and ExternalURL for the Web Services virtual directory are entered
The first fix was incredibly easy and after some more digging we determined this was only occurring when a client was external and logging in through an Edge server. When we looked at the Exchange Client Access Server we found this customer had not actually entered an ExternalURL parameter for the Web Services virtual directory. This works just fine for Outlook clients, but Lync is expecting this value to be filled out. If it's not entered it assumes EWS is not deployed externally and doesn't attempt a connection, which is a pretty reasonable action. You might argue the Outlook action is incorrect and it should treat it the same way. But anyway, the fix is to just fill out the ExternalURL and Lync will begin using that value to login to EWS successfully.
Sidenote 2: The information discovered by Lync via Autodiscover is cached in the registry at HKCU\Software\Microsoft\Communicator\<SIP URI>\Autodiscovery (Can you tell a Lync dev wrote the regkey name? Autodiscovery instead of Autodiscover?) You'll see entries for the internal and external URLs for the Availability Service, Exchange Control Panel, Exchange Web Services, and Out of Office Assistant. I've been able to delete this entire registry key for quick testing and found it recreated with no issues.
Solution 2: Place https://<Your SMTP domain>/ in the Local Intranet Zone
The second instance of this issue was a little more complicated, and still doesn't make much sense to me, but I figured I would share. In this case the customer did not have Outlook Anywhere published so we expected it to fail externally, but this error was actually occurring internally. After verifying the InternalURL was filled out correctly we started doing some traces and noticed the Lync client would make a GET request to the /Autodiscover/Autodiscover.xml file on Exchange, Exchange would return a 401 Unauthorized challenging for credentials like we expected, and then the trace died. There were be no more responses from the Lync client IP address sent to Exchange in the logs. We verified this on multiple machines and operating systems and concluded that the Lync client would never respond to the credential request! For what it's worth, Autodiscover was working fine for Outlook clients and no special configuration had been done to Exchange.
So we put a call into PSS and they told me Lync will not read the SCP for Autodiscover in AD, even if the Lync client is internal and that it will do its own Autodiscover lookup (Can anyone confirm/deny this?). Therefore, it will fall back to https://domain.com/Autodiscover/Autodiscover.xml, and if that fails it should move on to https://autodiscover.domain.com/Autodiscover/Autodiscover.xml like an Outlook client. This is where it got weird - PSS told me from the ETL trace Lync was not falling back to the 2nd option, yet I could clearly see it make a request to IIS and not respond. From what they saw the Lync client was getting stuck on the 1st option which didn't really exist. In any event, they had me add http://<domain.com>/ to the Local Intranet Zone on the client. Even though we knew this was not the location of Autodiscover and I really didn't think it would make a difference it did solve the problem. After adding entry this we saw clients then try to resolve autodiscover.domain.com and grab the Autodiscover.xml file correctly from https://autodiscover.domain.com/Autodiscover/Autodiscover.xml. At this point the EWS status in the configuration information returned to EWS OK.
Sidenote 3: There is a thread on the Technet forums about this issue which suggests editing your applicationhost.config file on the Exchange server. I have to recommend against this and as you can see in the comments it hasn't really fixed the problem for anyone. The solution is more likely one of the ones presented here.