В темные и страшные времена, когда, не выдержав физических и нравственных мук в застенках, бывалые бойцы покорно подписывали заведомо ложные обвинения, отрекаясь от самих себя, Анатолий нашел в себе силы и на суде бесстрашно обличать сталинщину. Почему его не расстреляли? По чистой случайности — как раз в это время ненадолго была отменена смертная казнь. Вместо этого ему предстояло заживо сгнить в лагерях. Шестнадцать беспросветных лет провел он там, но не погиб, не сломался и не согнулся:
В лагере, в нечеловеческих условиях неволи и каторжного труда, состоялось его поэтическое и нравственное становление. Там он ухитрился написать несколько циклов стихов и поэму о своем любимом герое — Франсуа Вийоне. Выбор героя его поэмы — не случаен. Именно великий французский поэт, вынужденный общаться с судьями и палачами, давал Анатолию силы выжить в беспросветных потемках ГУЛАГа, и выжить достойно. Да и соседями его подчас оказывались видные ученые — такие, например, как Василий Семенович Буняев — автор многих учебников по французской и немецкой литературе.
Пройдя все круги лагерного ада, Клещенко не согнулся, не ожесточился, не озлобился. Двадцатый съезд и реабилитация в 1957 году вернули его в родной Ленинград. По ходатайству Анны Ахматовой, Бориса Лихарева и Анатолия Чивилихина его заново приняли в Союз писателей, поэтому до самой смерти в его документах значилось, что он член союза не с тридцать девятого, а с пятьдесят седьмого. Приходилось все начинать с нуля. Стихи его не печатали. Александр Ильич Гитович помог ему с переводами — надо было на что-то существовать. И тогда Анатолий начал писать прозу («для денег», — говорил он сам). Его переводы тибетских народных песен, сделанные в 1957 году, сразу же получили самую высокую оценку Л. Н. Гумилева и Б. И. Панкратова.
В последующие годы в Ленинграде одна за другой стали выходить из печати его повести: «Дело прекратить нельзя», «Распутица кончается в апреле», «Когда расходится туман», «Это случилось в тайге». А вот стихи практически не печатали. Слишком горькими и обличительными казались они осмотрительным редакторам «эпохи застоя», подспудно замалчивавшей и обелявшей годы сталинских репрессий. Так появился писатель Анатолий Клещенко, а поэт как бы исчез.
Анатолию, однако, было душно в городе, где, по существу, мало что изменилось. Все, кто сажал его, остались на своих местах. Будучи человеком прямым и бескомпромиссным, он не мог спокойно чокаться в ресторане Дома писателей с доносившими на него стукачами, в том числе с преуспевавшим поэтом Николаем Новоселовым, чей донос сыграл роковую роль в его судьбе. На лето Анатолий нанимался сезонным рабочим в геологическую экспедицию и уезжал в тайгу и тундру.
После нашего неожиданного знакомства на Горбиачине мы не раз встречались с Толей в Ленинграде и в Комарово, где он жил рядом с Анной Андреевной Ахматовой. В шумных геологических застольях, где все звали его просто Толя, всегда поражали его скромность, сосредоточенность и немногословность. По его простецкому виду, бороде и постоянной трубке, с которой он никогда не разлучался, все окружающие принимали его за типичного геолога. Даже Анатолий Найман, ночевавший у него в те годы в Комарово, в своей книге об Анне Ахматовой не назвал его имени среди поэтов — соседей Анны Андреевны по Комарову, а на недоуменный вопрос вдовы ответил: «Я думал, что он геолог». О стихах его, и прежде всего о лагерных стихах, не знали даже самые близкие приятели. Вряд ли он надеялся когда-нибудь их опубликовать. За этим обликом неизменно скромного и доброжелательного «рубахи-парня» трудно было распознать героя, обличавшего всесильного злодея, и поэта трагической судьбы.
В то время стали известны песни Александра Галича, и Анатолий один из первых зазвал его к себе и записал на магнитофон. Потом он как-то неожиданно исчез из Ленинграда, а через год выяснилось, что он навсегда покинул Питер, завербовавшись на Камчатку в качестве инспектора охотохозяйства Елизовского района. Что заставило его сделать это? На это он сам отвечает в своем коротком стихотворении «Буран»: