As this took a few hours to find, it is worth a post here.
This history is not to be confused with the runMRU history which is apps that have been run, this is the AutoComplete history.
IE/CONTENT TAB/Delete Autocomplete History
As with most versions of windows some of the actual settings for it live in the IE menus. This is one of them.
Edit: AutoComplete in the Run box is set in (of course) Internet Explorer’s settings (Content Tab / AutoComplete): there’s a button to Delete Autocomplete History. If that doesn’t work, you could try turning AutoComplete off, rebooting, and turning it on again.
full credit to this posting