Communications Issues

In our domain, we are using Live Communications Server 2005 with Instant
Messenger 5.1 as the client on XP workstations. We use this strictly for
internal communications and do not allow the client to attach to the outside
world. On occasion, a user who is reported as online attempts to send a
message to another user who is shown as online, but after a few minutes
(usually not immediately), the sender is told the message was not received
because the recipient is offline ... or something similar. However, this is
not true as the recipient is online and if they (the original recipient)
initiate a new message to the original sender it goes through and then both
can communicate with each other.

We also have issues where users are sporadically logged out of IM for no
apparent reason. Normally, simply signing back on gets the user active again,
but there are times when we need to kill the msmsgs.exe process and then
re-launch IM to get on again.

Does anyone have any ideas on what might be going on and how we can correct
it? Thanks in advance.