Clear Windows "Run" box cache

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.

Try looking here: http://www.wikihow.com/Delete-Run-History-in-Windows

EDIT: I am on an XP machine, so I can't test this next bit, but does it work? http://windows.microsoft.com/en-US/windows-vista/Clear-the-Run-history-on-the-Start-menu

At least on Windows 8 the auto-complete history you are looking for is at HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\TypedPaths

A solid state OS drive and NirSoft's RegScanner and you're set to find anything in the registry quickly.