I use CCleaner too (it's fantastic!) and it can definitely be responsible for this. You could give it a try - get a couple of recent documents remembered and then run CCleaner to see if it clears them out. Any other cleaning software would also be a potential culprit.
To get the recent documents folder location you can
- click on the Orb > Open
- choose My Recent Documents on the left
- then at the top there's a drop down box which should say "Recent". If you click on that it should expand and it will show you the full path.
On my PC it's under C:\Documents and Settings\Colin\Application Data\Microsoft\Office\Recent