Clear the entries in HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\RunMRU
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.
Thanks to this link for the tip...
Clear Windows "Run" box cache | Newbedev
