オプション→ページ→履歴のクリアでは、確か消えないはず。
なんで？それは知らんけど・・・謎。
historyの削除ならイケルっぽいですね。
どーしても消えなかったら、リンクの色を細工するのがいいのでは？
デフォルトをブルーにして、行ったことのあるリンクもブルーに、
ぱっと見はわかんなくなっていい感じです。
ＩＥ４.０.１を入れちゃうのがいいかも、履歴のクリアもちゃんとできます。