As Burgerbob said, do it in the MSN Messenger Live first. Then go back to the config tool and if it's still there, do that again. What Emperor_nero and StrangleHold said basically does the same thing the config tool just did. Just different methods. So if you don't have it disabled in the program itself first, it will keep adding it on even after you when and disable/remove/unchecked it.
So, go do it in Messenger Live first.
Tools>Options>General
Make sure automatically run when windows starts up is unchecked