Windows Server 2012 / 2012 R2 と書いていますが、Windows 8 / 8.1 も同様になります。
Windows 7 の場合は、タスクバーのプロパティを開いて、[最近開いたプログラムを~] を一度無効にして、[適用] すれば履歴が削除されていました。
# 一度無効にして有効にすれば履歴は削除され元の状態に戻ります。
冒頭に書いた OS でファイル名を指定して実行の履歴を削除したい場合には、[最近開いたプログラムを保存する] を一度無効にすることで削除が行えます。
Windows 8 / 2012 以降はスタートメニューがなくなったのでどうなったのだろうと思って調べてみました。