Internet Explorerが消えた

「スタート」ー「コントロールパネル」の左側に見える「インストールされた更新プラグラムを表示」を
クリックしてその中のインターネットエクスプローラーを削除してみてください。

私が IE10 から IE9 に変えた時はうまくいきましたが。

元々すべてのプログラム・・・には存在しません。
WINDOWSの機能の有効化・無効化でチェックボックスがオフであれば存在しない
のは当然です。
チェックをオフにして再起動して、チェックオンにして再起動すれば復元する仕様
のはずです。

32 bit 環境なら C:\Program Files\
64 bit 環境なら C:\Program Files (x86)\ または C:\Program Files\ に
Internet Explorer というフォルダはありませんか？
あったらそのフォルダの中に iexplore.exe というプログラムはありませんか？

もしあったらそれをダブルクリックしてみてください。正常に立ち上がりますか？
もしそれがうまく行ったらあとは右クリックしてショートカットを作成してデスクトップなり
クイックランチャーなりにドラッグ・アンド・ドロップしてみてください。

上の条件に当てはまらない場合は他の方がいってるようにダウンロードからインストールし直しでしょう。

「スタート」「コントロールパネル」「プログラム」「プログラムと機能」上部「更新ファイルの表示」にチェック、表示されませんか？

既定でIEが入っているため(SP1はIE8 が基本)IE8はダウンロードできないと思います。IE9をダウンロードします。(但しメーカーサイドで、IE9 を OSの一部と化してインストールしている場合はIE9もダウンロードできない）

Program FilesのInternet Explorerからiexplore.exe右クリック「ショートカットをデスクトップに送る」またはショートカットを作成、デスクトップ画面へコピーし名前の変更でIE(2)の(2)を消す。

はじめまして、ご質問の件ですが、マイクロソフトサポートのホームページhttp://support.microsoft.com/kb/969174/ja
から、ダウンロードするのが一番手っ取り早く、確実だと思います。