u might want to update the comments about Ipod Messenger, since it now has an installer that patches msn messenger. Thus it doesn't matter where u have the installer.
As for skins, my Mad Skin works, so do Vibes Messenger and MUsn.
Take a look at
http://www.mad-skinning.net/skins/ for more info like screnshots and download links.