Where are they stored on the computer?

They can be found in the msmsgs.exe file
You need Resource Hacker or something to view or extract

Get resource hacker, and open up the msn exe file, click on the PNG folder and go down and find the folder 727 click on it and all the codes for the smiles are there, if you need the smiles, just pm me and i'll send you them.