To be truthful, I'm puzzled at the moment why the new install disappears when you re-boot.
First of all, you don't have to use IE to download CCleaner. If Firefox is your browser of choice, then I would use it for everything apart from the sites where you have to use IE such as Windows Update.
Sites will tell you if they're IE only access.
Second. I would suggest you uninstall the the older version of CCleaner using Add/Remove programs, but before you do that, if you have any settings such as Includes/Excludes, or a list of cookies you keep in Options\Cookies, then go "CCleaner\Advanced" and check the "Save all settings to INI file" box.
Then go into "C:\Program Files\CCleaner" and copy the "CCleaner.ini" file to another location, maybe your desktop, but anywhere really where you'll find it again.
After doing that, delete any copy of the latest version Installer in case there's a problem with it, and go to FileHippo, select "Download Latest Version", and save it to your desktop.
http://www.filehippo.com/download_ccleaner
Run the installer, and then check to see if that version is now in "Program Files\CCleaner". Just mouse-over the CCleaner.exe file and it will display the version number, which should be 2.26.0.1050. The exe file shows an extra 0 for some reason.
You can copy the CCleaner.ini file back to the CCleaner folder now to replace your settings.
Now reboot and see if it stays where it should.
You probably do all the stuff I've just explained, so apologies for that, but if I'm sure you have actually followed what is normal procedure, and the same thing happens, then we'll have to start scratching our heads for some other angle.