You will need to copy the custom sounds from your original Windows installation to your new one, and then run
Messenger Plus! Sound Library Fixer.
Messenger Plus! sounds are saved as .dat files and are stored in the following locations:
Vista:
C:\ProgramData\Messenger Plus!\Custom Sounds\
Windows XP/2000:
C:\Documents and Settings\All Users\Application Data\Messenger Plus!\Custom Sounds\
Windows 98/ME:
C:\Windows\All Users\Application Data\Messenger Plus!\Custom Sounds\