You are using Lync on a computer, and you are trying to send a new IM to someone who is using Lync on a mobile phone or device. You see the error message "This message may not have been delivered to {the other person} because the server sent the message to this person but it timed out.”
Or,
You are using Lync on mobile phone or device and you receive an IM notification from someone using Lync on a their computer. After about a minute, you see a "Missed conversation" alert.
In this scenario, Lync is working as expected. If the person using the mobile phone or device misses the IM notification (because Lync is running in the background, the phone or device is locked, or they simply don't see the notification) Lync determines that the IM was missed. Lync then notifies the sender that the IM might not have been received. The person using the mobile phone or device can still access the IM by looking at their chat history.
During an IM conversation with someone who is using Lync on a mobile phone or device, you see the error message "This message may not have been delivered to User B because the server sent the message to this person but it timed out.”
You are using Lync on mobile phone or device during an IM conversation and you happen to miss a response from the other person because Lync is running in the background and you are busy with something else. You check your chat history but their response isn't there.
This behavior is also expected because an ongoing conversation like this one is not captured in the chat history. Only invitations to new conversations are captured there.
<Please add links to similar problems or solutions>
Richard Mueller edited Revision 3. Comment: Fixed duplicate <a name> tags in headings in HTML so TOC works properly, added tags