I'm sorry to post to such an old topic. This thread is one of the top hits on google for the topic, and I think it deserves a good answer.
The maximum size of normal MSN emoticons (without plugins or addons) is 50x50 pixels. To get the maximum size, your emoticon has to be an animated gif file. This means that even emoticons that don't look like animations have to have at least two frames, even if the frames are identical.
If the emoticons is not in the correct format, MSN will shrink it to a measly 19x19 pixels.
Luckily, there are tools that do the work for you, and they are a lot quicker than going through the motions in Photoshop.
I recommend
http://www.emoticonize.com.
If you want to do it by hand in a paint program and you have a picture that is not animated, you might end up in trouble. Many animation tools "optimize" the identical frames away, leaving only one frame. MSN doesn't like that. You could try changing one pixel to a slightly different color, if you can't turn the optimization feature off.
/ 
