Windows Messeenger

I have a problem with Windows Messenger 4.6-its does not allow me to sign in to exchange instant messaging showing error msg “The person logged onto this computer does not have permission to use the specified e-mail address…” I use the correct credentials!Even after uninstalling and reinstalling the problem remains. The only way out I haver ever had was to to format and re-install the O.S.Is there any other better solution?