Hi. I have had a problem in the past with Exchange Messenger not logging in and have found one or other of the following usually solves it:
In User Properties for one of your users who is experiencing the problem, click on the Exchange Features tab. In the feature list, Instant Messaging should be enabled. If not then enable it. When creating new users this is set by default to disable.
If this is not it then how do your users log on to the Messenger. Is it in the format of username@servername? If so have you set up your server name in the Hosts file of the computer which is having a problem. E.g. the username is tom and the Exchange Server name is exchserver, so your IM user logs on as tom@exchserver. If the IP address of the Exchange Server were 10.0.0.2 then in your Hosts file, create a line 10.0.0.2 exchserver. Hosts can be found in C:\Winnt\System32\Drivers\Etc on NT4/2000. In XP it is Windows rather than Winnt, but all else is the same.
HTH
Stuart