It happens on both pc's here and the configuration is a bit different. 
My own pc:
Windows XP Service Pack 2 (5.1.2600)
Windows Live Messenger 8.01.0168
Messenger Plus! Live 4.11.0.254
StuffPlug 3.0.286 BETA
Polygamy using Msgplus! Multiple Accounts
The other pc:
Windows XP Service Pack 2 (5.1.2600)
Windows Live Messenger 8.00.0812
Messenger Plus! Live 4.11.0.254
Polygamy using Mess Patch polygamy
Active scripts both PCs have in common:
- Activity Launcher
 - Email tooltip
 - File Transfer Plus 1.1
 - Key Flasher
 - Now Playing
 - ReduceMEM - Cookie Style 

 - xPSM v1.1
 
It happens on both pc's on Windows startup, no shortcut involved. Both pc's only have one 
msnmsgr.exe /background entry in 'msconfig'.
When checking the registry keys you mentioned, only the HKCU-key got a msnmsgr entry (and 
only one), not the HKLM one. 
No 3rd party startup program for Messenger or something.