Consider the following scenario. You use Microsoft Lync Online through the Business Online Productivity Suite (BPOS) together with an on-premise Exchange server. In this situation, Lync 2010 prompts you for credentials when it is retrieving availability data through Exchange Web Services.
This issue occurs because Lync 2010 does not always try to use the default Windows NT LAN Manager (NTLM) credentials when it is retrieving availability data from the Exchange Web Services.
To resolve this issue, install the following cumulative update:
2496325 Description of the cumulative update package for Lync 2010: April 2011
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.