Excelを起動させ、適当なセルで右クリックし、「ハイパーリンク」を選択する。 
すると、「ブラウズしたページ」「最近使ったファイル」として、履歴が丸見えになってしまう。
これらを削除する方法について残します。

因みに、当環境は、
Windows7　＆　Office2007　＆　IE9です。

＜「ブラウズしたページ」の削除方法＞
これは、IEの履歴を見ているので、IEの履歴を削除すればOK。
IE開いて、「インターネットオプション」「閲覧の履歴」から「削除」を選択して履歴を削除。

＜「最近使ったファイル」の削除方法＞
C:\Users\「username」\AppData\Roaming\Microsoft\Office\Recent
の中身を削除。

＊WindowsXPの場合（この情報は、調べた際に出てきた情報ですので、試してません）
C:\Document and Settings\「username」\Application Data\Microsoft\Office\Recent 

上記作業で、私の環境では問題なく履歴が削除出来ました。

＊＊＊
本作業は、ファイル（一時ファイル、ショートカットファイル）の削除を行う為、各々の自己責任で
作業して下さい。何が起きても私は責任を取れません。
＊＊＊