Messenger 5.1 Exchange problem

I have a client that runs Windows Messenger via Exchange. Many, but not all
of their machines have this problem:

I can install Messenger 5.1, unselect SIP, unselect .NET, get them connected
under the Exchange option and it works fine. Turn the machine off, turn it
back on, and Messenger will not connect. When you look under Options->
Accounts the option for Exchange is missing! It will ONLY show SIP and .NET
as the choices.

A work-around is to run the install for 5.1, choose repair, and they can
connect. I really don't want the user to run the install and repair every
morning just to connect. I am writing to you after exhausting all of the
obvious (I've uninstalled Messenger from A/R programs and re-installed using
the local admin account for the machine, tried various 'messenger uninstall'
tools available, etc.)

I am desparate, and really hope to find the solution soon.

Justin

More info: The server is Windows 2000 Server, Exchange 2000, clients are all
XP SP2, latest updates installed.