When your Run History is always cleared after a restart,this is caused
by a registry entry responsible for the Recent Documents histrory.
It delets the Run history as well :

- HKEY_CURRENT_USER
\Software\Microsoft\Windows
\CurrentVersion\Policies\Explorer\

In the right pane select the entry :

ClearRecentDocsOnExit

(Double click it and set it's value to 0 to disable it,1 enables it)


You can clear the Run History as well by deleting the entries
in the right pane under :

- HKEY_CURRENT_USER\Software\Microsoft\Windows
\CurrentVersion\Policies\Explorer\