Sounds like Messenger is configured to start in two places, most likely All Users and within a user profile. You will have to look in the registry to find this. Search for loadqm.exe in run Run key of HKLM and HKCU, should probably only be in one of these places. Where, depends on the network configuration, meaning is it loaded with the profile, or loaded for all users per machine...
Regards,
Mike Tao is the mobius. The ribbon of heaven and earth, you cannot lose your way.