Hi cursty, I'm using Registry Mechanic 7.0.0.1010, and CCleaner doesn't erase my registration details, and it's strange why it's removing yours.
However, computers are weird, and this may help. My reg details are held in a registry key, as below:

Navigate to the highlighted registry address. Start > Run > type in "regedit" (no quotes) > navigate to:
HKEY_CURRENT_USER\Software\Microsoft\Search Assistant\ACMru\5603 (the number may be different, not sure).
If your details are there, in regedits menu select "Edit > Copy key name" (just left click the "copy key name").
Now open CCleaner and navigate to "Options > Exclude > Add Registry".
In the small box of the address bar, select HKCU from the drop down menu.
Now, right click in the address bar and select paste.
After you've pasted the address you will have to delete the hive name ie "HKEY_CURRENT_USER\" from the beginning of the pasted address as it's already selected in the first box.

The "OK" button should now become active. Select it, and your done.
See if that does the trick and come back and let us know.