It just crashes every time? If you've ripped and reinstalled the app then you've buggered up something in Windows. Troubleshooting that becomes... bothersome.
If you really wanna try it, uninstall the app again. Then find where it would physically sit on the hard drive (probably c:\program files\windows messenger or something) and delete the directory. Also delete other places it might hide stuff, like in your application data folder (C:\Documents and Settings\Administrator\Application Data) or maybe your local settings (C:\Documents and Settings\Administrator\Local Settings\Apps). Also clear your temp folder in case that's jacked up and causing your reinstall to go stupid (C:\Documents and Settings\Administrator\Local Settings\Temp). For all those, substitute your username for administrator. And if you're on Vista you may need to figure out where it is... I think it'd be like c:\users\administrator or something instead of document and settings.
once you've done all that, go in the registry and clear out as much crap as possible. Some good places would be
HKEY_CURRENT_USER\Software\Microsoft
be sure to find the folders for Live Messenger. Don't just delete the whole Microsoft key or your pc won't boot.
Also try HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft.
Once all that done, reboot, then try reinstalling messenger. If it still doesn't work, maybe consider an alternative like pidgin.
Because the next step would probably be to just reinstall Windows or get professional help.