It seems that there could be a flaw (feature?) in the new version of Windows Messenger (4.7), which enables Messenger to sign you in, without permission, and without your knowledge.
I installed it the other day, and precisely that happened. I had no taskbar icon to indicate WM was even running, let alone that I was signed in. My only notification was when chat windows started popping up. I opened the Tools section, and made certain the box to 'Load Messenger when Windows starts' was un-ticked. I even deleted my password, so that it could not sign in, but it still did.
I thought it was just me and my PC, but I have spoken to two other people who have found the same problem. I would advise anyone considering upgrading to the new version of WM to stick to the old version, until this issue is resolved.
If you want to un-install Windows Messenger, it doesn't appear in Add / Remove as it's integrated with XP, but here is a useful link to get rid of it if you need to -
click here.
I don't know if the above applies to the new version of MSN Messenger. I haven't tried, and will be sticking to Trillian for now.