It does not sound like a registry issue since you can still see the Run command, but here are the entries that I know, hope it helps.
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer
And
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer
Value name NoRun
Data Type REG_DWORD
Value Data – 0=disabled 1=enabled
Here are some additional registry entries for the run window
[Start] [Run] [Regedit]
Registry Key: HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\ Policies\Explorer
Create a DWORD value for each Run function that will be disabled.
Modify/Create the Value Name [DisableLocalMachineRun] according to the Value Data listed below.
Data Type: REG_DWORD [Dword Value] // Value Name: DisableLocalMachineRun
Modify/Create the Value Name [DisableLocalMachineRunOnce] according to the Value Data listed below.
Data Type: REG_DWORD [Dword Value] // Value Name: DisableLocalMachineRunOnce
Modify/Create the Value Name [DisableCurrentUserRun] according to the Value Data listed below.
Data Type: REG_DWORD [Dword Value] // Value Name: DisableCurrentUserRun
Modify/Create the Value Name [DisableCurrentUserRunOnce] according to the Value Data listed below.
Data Type: REG_DWORD [Dword Value] // Value Name: DisableCurrentUserRunOnce
Setting for Value Data: [0 = Disabled / 1 = Enabled]
Exit Registry and Reboot
AJZ