"The following message could not be delivered to all recipients" MSN messenger v5

Hello all,

We've been using MSN/Windows Messenger (version 4.something before, now
5.0.0482) with [only] Exchange 2000. It was working great for a year or so,
but now we're having sporadic problems. I have Googled for hours without
success.

The Windows Messenger connects fine when you sign in. It shows contacts and
appears functional. I have ensured that each Exchange user has the Instant
Messenging feature enabled--I assume since they connect that is true.

The interesting part is that when you sign in, it broadcasts this message to
all the users, so some data is getting to the clients. When you go to IM
someone, it says "The following message could not be delivered to all
recipients" BUT, sporadically, you can IM 1 person, but not another--often
enough that person that was IM'd cannot reply! Then if you sign out, you
cannot send/receive to that 1 person anymore.

I did try re-creating the IM RVP server in Exchange by deleting the RVP
service. I followed the Microsoft (#266643) article on how to setup IM
Server. Still same results. It even kept the contacts--including contacts
from domain users that were deleted and purged several months ago. I did
notice that Outlook Express (we only use for usenet) had those [old and
purged] contacts and I deleted them from there. When I opened up my Exchange
SDK VB sample, it still found those old users. In fact, it had about 10
users that have been deleted/purged over the period of a year or so :|

I went into the Web logs where the IM server is located and found many
lines, including this one. It has my IP (.12) sending to the server to user
"userslogin" with the 500 error (Internal Server error--well that's what it
has been for me in ASP).
192.168.12.12 80 192.168.12.19 NOTIFY
/instmsg/aliases/userslogin - 500 -

When I open up the Exchange SDK for the VB client, it logs in fine. When I
try to send a message to message to a user, I get:
"> Method 'SendText' of object 'IIMSession' failed"

I realize that Messenger goes through IE. So, I have done what several of
the posts said to do. Unchecked the "revoked cert" (that sounds dangerous),
ensured that SSL's were checked, I added the domain to the trusted sites,
re-registered several DLL's, set the security levels to default....Nada, zip

The only thing I haven't done is uninstalled the IM from Exchange and
re-installed it. I don't think "Repair" has ever been effective for any of
the products I have used. I'm wary of that since it's a production server.

Is there a way to "clean" out the IM feature to rid it of anything that may
be causing this type of issue? Is there any other information that I have
not provided that would help with diagnosing and fixing this issue?

Thanks for any input/help/advice/anything that you can give!

Cheers,

Rich