C:\Documents and Settings\(whatever your username is)\Application Data\Microsoft\MSN Messenger\(your messenger account)\CustomEmoticons
You'll find them stored as .dat files not the expected .jpg .gif or .png and will have rather cryptic names like "TFR23.dat". If you want them to be restored to their proper extensions all you have to do is open them in a program like irfanview and it will recognize the incorrect extension and offer to correct it.