Indeed, "just format c:" should never be a solution, certainly not a solution recommended by big companies
.
But without an error message its hard to figure out the cause, only thing i can think of if you haven't done so already is uninstall/delete the drivers and uninstall Live Messenger completely. Make sure these folders are gone (backup things like emoticons and display pictures if needed):
C:\Program Files\MSN Messenger
C:\Documents and Settings\<USERNAME>\Application Data\Microsoft\MSN Messenger
C:\Documents and Settings\<USERNAME>\Local Settings\Application Data\Microsoft\Messenger
After that get the latest public Live Messenger version from
http://get.live.com/messenger/overview and try again.
/ 
