I can send, but not receive

I use Windows Messenger (previously 4.7, now trying with 5.0),connecting to our internal Exchange server

While the system has worked in the past, at some time in the last month or two stopped working properly. There's any number of software updates and the like I've done in that time frame, so, unfortunately, the "what's changed on your computer" question is way too big to answer. :-

The current behavior is that when I sign in, it does so just fine, updates the status on my contact list, etc. I can send out messages that are received, but others cannot reply back to me (sometimes they get an error that I'm not available, sometimes not, but in either case, I see no response). Nor does my contact list status ever get updated

It's not an account problem, since I can go to another person's machine, sign into WM there, and it works perfectly. It's machine-based

I've tried uninstalling WM (running the 4.7 rundll32 unnistall, deleting the directory, zapping Registry entries I could find), but the 5.0 install always just specifies Repair, so I'm missing something somewhere -- and Repair never fixes the problem

I am, so far as I can tell, not using an odd proxy or behind a firewall or anything like that. This is occuring here in the office, on the same WAN, and I communicate with with that Windows domain for Exchange e-mail without any difficulty

Our internal Messaging folks suggested reinstalling Office, which I've done, to no avail. Their next suggestion is scraping the system down to the bedrock and rebuilding it, which is a fate worse than death (or at least worse than never using WM, which would be only just really irritating)

Any ideas of what might be wrong, or what I might look into to further diagnose the problem?