If I uncheck the entry, MS ICE starts quickly. If I allow CCleaner to remove it, MS ICE essentially re-installs. I'm sure CCleaner thinks it is doing the right thing, but I don't think it should be doing this :-)
your program writes the registry key in a way that make CCleaner see it as unlinked. there are millions of unlinked registry keys; it would be impossible for CCleaner to keep an "in-built" list of one to exclude, thus the developers have provided an easy way to never see the entry again. In fact it is now even easier to do.
Run an "Scan For Issues" in the registry section]
Right click the entry you wish to exclude
Choose "add to exclude list"
The Item will no longer show up
Be sure, if you uninstall the program, to remove the exclude (in case the program leaves the entry after uninstalling, which is kinda highly likely).
and see my signature for advice in using Ccleaner's Registry section (or that of any registry cleaner, a class of which CCleaner is considered gentle)