One day, for no apparent reason, my Windows Live Mail decided it wouldn't start no matter what I did. After searching this and other resources, and trying the suggested solutions, I finally came up with my own. This is what worked for me, hope it helps someone else:
1. I had a look at the log files, located here: C:\Users\(MY-USERNAME)\AppData\Local\Microsoft\WLSetup\Logs
They all seemed to start OK but then hang at the same place. The last line in the log file said "Cert :00000900 (06/29/2012 20:12:10.094) Verifying signature of file=[C:\Users\__USERNAME__\AppData\Local\Windows Live\.cache\LOO5rDp5hbmHg5sboPPgQ2mUlhc=]..."
2. So I deleted the whole C:\Users\(MY-USERNAME)\AppData\Local\Windows Live\.cache folder. Restarted my PC and tried once more. Live Mail was "Live" again!