Clear Windows "Run" box cache

One thing that I use almost every minute is the Windows Run box (WINDOWS+R). It let's you type a path and auto-completes it really quickly so that you can jump to any dir in no time.

My problem is that I recently swapped disks and re-organized content so a few of the drive letters changed while most (but not all) the dir structure stayed the same. Now the auto-complete is giving me a lot of old results that don't physically exist anymore and it's not only annoying but the advantage of speed is not there anymore because I now have to check for old results in my auto-complete!

How can I clear that auto-complete's cache?

Thanks!

EDIT: I'm not talking about how to clear the last run items from the Windows Start menu. This is completely different. What I'm talking about auto-completes directories in the file system and is "remembering" old auto-completed paths (which are NOT programs, just paths).

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.

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.

I would do it the following way:

1. Get SysInternal's Process Monitor
2. Filter to "Explorer.exe" as the process/file
3. Execute Win+R
4. See what is happening in Process Monitor (I assume that some registry/files are involved)
5. See whether you can delete those found entries/contents.

Update

Seems others have better answers than I, please see those for a direct solution to your question.