I have had the same problem since I started using Windows 7. I wrote about it here months ago, was given the same answers regarding CCleaner and Internet Options, and neither of those suggestions worked.
Now, I just googled again, and finally found the answer, in a different thread on these forums: start/run doesn't remember my previous types ,why?
Starts with the same ccleaner response, but go to the fourth post in that thread, by Fayla. The answer lies there--it is in the options for the Taskbar and start menu. RIght-click the taskbar, choose properties, select the second tab-"Start Menu", then look under "Privacy". Both options should be checked, and then you will get the run menu history. It worked for the OP in the thread above, and just worked for me.