Я к CCleaner , как-то не очень отношусь , мне больше нравиться
TuneUp Utilities .
То что дело в оси это факт .
Adobe оставляет хвосты везде и в папках пользователей ( причем как правило во всех ) и в Common Files и в Program Files - я например не стесняюсь и сразу теру такие вещи ( с этими папками вообще не встает ни че ) .
Скачай кокой-нить редактор реестра накачанный ( я пользовался
Reg Organizer ) , а CCleaner видит эти ключи от Adobe просто не удаляет их и думает , что продукты Adobe работают в норме - придется удалять в ручную .
По средствам Reg Organizer искать такие слова , как Adobe , во всех раздалах реестра во всяких software и т.д.
Тогда что-нить получиться .
Так же сделай резервную копии реестра и погнал .
Можно так же автоматом прогнать пару раз в расширенном режиме , только он в автоматическом режиме , когда не знает , что делает просит вмешательство пользователя ( в таких случаях я просто удалял и все ) .
А если удалишь , и ось накроется медным тазом не беда у тебя ведь
сделан backup перед всем содеянным 
, а ось в данном случае и так и так придётся менять если очень нужен Photoshop .
Еще в Total Commander-e есть плагин по редактированию реестра , тоже не плохой .