How are you removing it from start-up? With msconfig?
I don't use it, so I can't tell you step by step, but somewhere in options or preferences in MSN Messenger itself, is a box to uncheck if you don't want it to load at start-up. Have you done that?
Every time I use MSN Messenger it loads itself in Start up so next time I boot the computer it opens. I remove it and it's gone as long as I don't use the program. How can I keep it from loading in Start Up.