Every now and then I move to a new computer and try to IM someone using one of my custom emoticons only to find that the picture doesn't show up. Luckily, it's as simple as copying some files from your old machine.
Simply go to
C:\Users\User Name\AppData\Local\Microsoft\Messenger\Live ID\ObjectStore\CustomEmoticons and copy the files in there to the corresponding location on your new PC. Remember to replace User Name with your own user directory and Live ID with the email address you use to sign into messenger.