スタートメニューの「最近使ったファイル」に表示されるショートカットだけを削除するには、ショートカットが保存されている Recent フォルダを直接開いて削除します。

Windows 2000/XP では、C:\Documents and Settings\（ユーザー名）\Recent　…隠しフォルダです

Windows 95/98/Me では、C:\Windows\Recent

Interner Explorer のアドレスバーの履歴と、「ファイル名を指定して実行」も削除されて構わないのであれば、「最近使ったファイル」の [クリア] で削除されるものの方法が簡単です。