Error: the following message could not be delivered

I get this error when I start a conversation with one particular WLM contact.
All my messages to this contact get rejected until I close the IM window, and
the contact initiates the IM session with me. Once the other person
initiates an IM session with me, my messages to the person are successful.

This contact is having the same problem with the other people who attempt to
IM him. Nobody seems to be able to contact him, until he contacts them first.
The contact and I are using WLM v2008 Build 8.5.1302.1018.

I dont have the problem with other people I send IMs to.

Googling this error message shows forums in which other people have been
reporting this problem for over a year, but no solutions. One possible tip
was to reset message logging. This contact and I are not logging messages.

Thanks for any guidance.