In Windows Explorer > Tools > Options > Folder Options > View > Files and Folders, enable Show hidden files and folders.
You should now be able to see C:\Documents and Settings\[USERNAME]\Local Settings\Temporary Internet Files. I recommend using the Details view. There may be a lot of files in the folder but if you sort by Name (Favicon.ico) or by Type (Icon), you can locate the icons quickly. If you've previously lost your icons, you may need to add the Favorites again to reload the icons. Copy the icons to a folder which won’t be cleaned, e.g., My Pictures > Icons. I would rename each, e.g., CCleaner.ico
Then right-click a Favorite shortcut (in the Favorite folder or in the IE dropdown) and click Properties. In Properties, on the Web Document tab, click Change Icon. On the Change Icon panel, click Browse and navigate to the saved icon. Select it and click OK.
You could just do the last step for any Favorite where the icon is already available, e.g., since the CCleaner icon is embedded in CCleaner.exe, if you navigate to C:\Program Files\CCleaner\cleaner.exe, it would be available there for use with a CCleaner Forum shortcut.
I've never tried amdeadlink but this method allows you to customize any shortcut, e.g., Desktop folders, Start Menu program folders (use the Properties > Customize tab or the Properties > Shortcut tab depending on type).