The Start Run (open) autocomplete history is actually controlled by Internet Explorer
Tools -> Options -> Content -> Autocomplete
If you want to erase the history, after removing the above you can then choose General -> Delete -> Delete all
(yes, this will "lose your saved usernames and passwords")...
This can be done as a security feature OR if you've got a bunch of "helpful" autocompletions to links or documents that no longer exist.