IE以外のアイコンがすべて対応ファイルなし状態のアイコンに変化し変化したアイコンのアプリケーションが起動しない状況です。

「○○を○○したらアイコン表示がおかしくなった」かがわからないと、具体的な回答は難しいかもしれません。

また、その壊れたアイコンをダブルクリックしたときに、通常通りアプリケーションが起動するのかしないかによっても

回答が変わってくるかと思います。

とりあえず一般的な現象としては、アイコンキャッシュがおかしくなってしまった可能性があるかと思います。

Windowsではアイコンを表示するとき、毎回アイコン画像を探すと処理が重くなってしまうので、

アイコン画像を高速に探せるように、アイコンキャッシュというものを作成します。

アイコンキャッシュは１つのファイルになっているのですが、そのファイルが壊れてしまうとアイコン画像がおかしくなってしまいます。

その場合の対処療法としてはそのアイコンキャッシュのファイルを削除する、ということになります。

以下のサイトにまとめられていますので、参考にしてください。

ただし最悪Windowsが動かなくなってしまう可能性も0ではありませんのでご注意ください。

http://www.yoshibaworks.com/ayacy/inasoft/skr/iconcache.html

あれ、リンク見れませんでしたか。自分のPCからは見れていました。Googleのキャッシュ版を紹介しておきます。

http://72.14.235.104/search?q=cache:waBzAqZx5noJ:www.yoshibawork...

ただこれはアイコン表示だけがおかしいときに有効なので、exeを実行しても起動しないとのことであれば違うかもしれません。

他の方法としては、

http://pasofaq.jp/windows/startmenu/exefile.htm

というのもあったりします。

ただ、いずれにしても問題に対する対処療法であるので、結局根本的な原因がわからないと

また発生してしまうかもしれませんですね。

ハードウェアが原因の可能性もあるので、可能であればオンラインゲームをインストールしない状態でしばらくPCを使っていて、

それで現象が起きるかどうか見極めができたりするとよいかもしれません。

（ハードが原因だと仮定すると、オンラインゲームでPC内部に高負荷がかかり、その結果熱暴走を起こして

PCが勝手に再起動してしまい、突然再起動されたのでWindowsの何かを破壊してしまった、など）

力不足な回答ですみませんです。