Es raro ya que yo no los perdi al instalacion la ultima version, sobre los iconos creoq ue se encuentran en :

C:\Documents and Settings\Tu nombre de usuario\Datos de programa\Microsoft\MSN Messenger\2735536942\CustomEmoticons

Para ello tienes que activar ver carpetas ocultas.

P.D existe un programa llamado messenger deluxe que ocupa aprox. 26.2 Kb ,al ejecutarlo te da acceso para coger emoticonos gratis,ademas de que hay muchos. te lo podras descargar desde MessengerAdictos