I think they're held within the MSN files themselves. I notice whenever MSN release a new version custom smileys die too lol.
If you have more than one computer you could send all your smileys to one's messenger, update the other, then send all the smileys back and update.
There might be software to backup smileys, but I dont know of any.
SiriusB