状況からすると、メッセージストア内のデータを読み込めずに動作停止してしまっているのかもしれませんね。
もし、奥の細道さんがおっしゃっているやり方でうまく起動できるようになれば、それはそれでいいのでしょうけど、
仮にやってもうまくいかないようであれば、Windowsメール自体はそれのみを再インストールできるものじゃありませんから、
もし試すとすれば、一度メッセージストアを再構築してみて正常にデータを読み込んで利用可能になるかどうか?
ご確認になることぐらいのような気がします。
http://support.microsoft.com/kb/941090/ja
上記のサイトの、"高度なトラブルシューティング"のところにに、バックアップのとりかたから、
再構築の方法まででていますので、もしできそうなら試されてみてはいかがでしょうか?