Premetto che la seguente procedura è stata provata (da me) senza aver formattato.
1. Chiudere messenger (non disconnettersi e basta ma proprio chiuderlo)
2. Portarsi in questo percorso... C:\Documents and Settings\Nome utente\Dati applicazioni\Microsoft\MSN Messenger\*cod numerico*
3. Salvare la cartella CustomEmoticons
4. Ripristinare nello stesso percorso la cartella dopo aver formattato ed aver reinstallato MSN Messenger.
P.S: Ripeto che questa prova l'ho fattta senza aver formattato ed ha funzionato perfettamente non avendo trovato nessuna soluzione al tuo problema. Ovviamente non mi prendo nessuna responsabilità sulla cattiva riuscita dell'operazione. :)