По многим причинам работа по реабилитации не была свободна не только от бюрократических недостатков, но и от принципиальной несправедливости. Реабилитация расстрелянных или умерших в лагерях заключенных проводилась только по заявлению родственников или друзей. Если по делу не было заявления, то его не рассматривали. Когда такая реабилитация все же проводилась, например, по групповым делам, то никто не разыскивал родственников или детей умершего, чтобы сообщить им о реабилитации и выдать положенную в таких случаях небольшую компенсацию. Не проводилась формальная реабилитация участников оппозиционных течений 1920-х годов, хотя их и освобождали из заключения или ссылки, если они еще были живы. Не был проведен пересмотр фальсифицированных судебных процессов 1930-х годов.

Вдова H. Н. Крестинского в течение семи лет после XX съезда добивалась реабилитации своего мужа, проходившего по делу «правотроцкистского блока» вместе с Н. И. Бухариным. Когда ей наконец сообщили, что ее муж реабилитирован и восстановлен в рядах партии, она умерла от инфаркта, упав на пол рядом с телефонным аппаратом. Вдова Бухарина не могла добиться реабилитации мужа и через 25 лет. Остались если уже не в списках «врагов народа», то в списках «антипартийных деятелей» Томский и Рыков, Каменев и Пятаков, Шляпников и Рязанов, а также многие другие крупные деятели партии и государства.

Никто не привлекал к ответственности следователей НКВД, проводивших «дознание» с применением пыток, начальников лагерей и тюрем, надзирателей. Тем более не обнародовались имена доносчиков, даже если это была очевидная клевета. Тем не менее, как только началось возвращение домой бывших заключенных, многих доносчиков и следователей охватила паника. Были случаи помешательства, даже самоубийства.

В психиатрической больнице оказалась, например, известная тогда деятельница комсомола Ольга Мишакова, по доносам которой в 1937–1938 годах были арестованы многие руководители ЦК ВЛКСМ. После реабилитации этих уже погибших людей Мишакова была снята со своих постов и уволена из центрального аппарата ВЛКСМ. Но она была уже неспособна понимать происходящее и по-прежнему каждое утро приходила в свой кабинет. Когда у нее изъяли пропуск в здание ЦК ВЛКСМ, Мишакова впала в буйное состояние, и ее пришлось госпитализировать.

Один из бывших следователей, теперь уже полковник внутренних войск, узнав на улице своего давнего узника и подследственного, упал на колени и умолял о прощении. Другой бывший следователь, узнав в соседе по больничной палате свою жертву, умер от сердечного приступа.

Но были и другие примеры. Когда директор школы из Северной Осетии после многолетнего заключения и реабилитации пришел в свое министерство и узнал в министре просвещения Осетии своего бывшего следователя, то инфаркт случился не у министра, а у бывшего директора школы. В Киеве реабилитированный и вернувшийся в армию офицер, встретив когда-то пытавшего его следователя, застрелил его из пистолета.

Но такие случаи были очень редки, и беспокойство среди работников НКВД, принимавших участие в репрессиях, как и у всех других активных участников беззаконий сталинского времени, быстро улеглось. Общество пробуждалось от тоталитарного оцепенения очень медленно. К тому же большинство узников сталинских лагерей давно покоились в братских могилах с номером на деревянной бирке на ноге.

Впрочем, большинство из тех, кто вернулся из лагерей, испытывали в первые годы не столько гнев или жажду мести, сколько страх перед возможными новыми репрессиями.