I had this problem as well even though i set msg plus to start at startup, it didnt always.
I downloaded
AppLoader which lets you start MSN Messenger and plus at the same time and make it executable by a shortcut. I then put this shortcut in my startup and unchecked the things that make MSN and plus run at startup and i have never had the problem again.
Hope this helps