Another handy program is CCleaner. Cleans up your computer from internet stuff, registry cleaner, and has a add/remove/start-up function. You can just go to the Start-Up screen and highlight msn messenger and delete/no start.
There's multiple ways of stopping MSN from starting but CCleaner is just a nice all around tool to have.