Реабілітація була довгою справою. Прохання про реабілітацію мали надходити від самих в’язнів або їхніх родин; щоб це прохання задовольнили, потрібно було писати по два, три, а то й набагато більше разів. Та навіть після начебто успішного закінчення цей нелегкий процес часом міг повертатися назад: Антон Антонов-Овсєєнко отримав посвідчення про посмертну реабілітацію свого батька, яке 1963 року було відкликане[1850]. Багатьох колишніх в’язнів цей процес подачі клопотань і очікування результатів дуже виснажував. Ті, хто отримували виклики з’явитися на засідання комісії, яке зазвичай відбувалося у відділеннях МВД чи міністерства юстиції, часто, вирушали туди із запасом одягу і харчів, супроводжувані плачем рідні і певні того, що їх знову відішлють ні з чим назад[1851].
На найвищому рівні радянської влади існували побоювання, що процес реабілітації може піти надто швидко і зайти надто далеко. «Ми боялися, справді боялися, — згодом писав Хрущов. — Ми боялися, що відлига може спричинити потоп, який ми не зможемо контролювати і в якому потонемо»[1852]. Колишній старший слідчий КГБ Анатолій Спраговський згадує, що у 1955–1960 роках він під час відряджень у Томській області опитував свідків, бував на місцях, де начебто відбувалися злочини. Серед іншого він дізнався, що колишніх в’язнів звинувачували у змовах з метою висадження в повітря заводів і мостів, яких насправді не існувало. Та коли Спраговський написав Хрущову, пропонуючи спростити і пришвидшити процес реабілітації, він отримав категоричну відмову: здавалося, що московські чиновники не хотіли, щоб помилки сталінських часів виглядали надто значними чи надто абсурдними, як не хотіли вони того, щоб перегляд старих справ ішов надто швидко. Анастас Мікоян, член сталінського політбюро, який залишився при владі і за наступного радянського керівництва, одного разу пояснив, чому неможливо реабілітувати людей надто швидко. Якщо їх усіх відразу проголосити невинними, «то буде ясно, що країною керує не законна влада, а зграя бандитів»[1853].
Комуністична партія теж остерігалася визнати надто багато помилок. Хоча було переглянуто понад 70 тисяч справ колишніх партійців, які вимагали поновлення свого членства в партії, з них було задоволено менше половини[1854]. В результаті всього цього повна соціальна реабілітація — з повним поновленням прав на роботу, житло і пенсію — залишалася дуже рідкісним явищем.
Набагато поширенішим за повну реабілітацію було те, що переживала і відчувала Ольга Адамова-Сліозберг, яка 1954 року подавала документи на власну реабілітацію і реабілітацію свого чоловіка. Два роки вона чекала. Потім, після таємної доповіді Хрущова 1956 року, вона отримала довідку. У ній ішлося, що її справу було переглянуто і закрито за браком доказів. «Арештована я була 27 квітня 1936 року. Значить, я заплатила за цю помилочку 20 роками 41 днем життя». Як компенсацію їй призначалося двомісячні оклади — її і її чоловіка, і ще 11 рублів 50 копійок за 150 рублів, які були у її чоловіка у момент смерті. І все.
Стоячи у приймальні Верховного суду в Москві і осмислюючи новини, вона почула, що хтось кричить. Кричала стара українка, яка щойно довідалася про схожі новини:
«— Не потрібні мені гроші за кров мого сина, беріть їх собі, убивці. — Вона розірвала довідки і жбурнула їх на підлогу.
До неї підійшов військовий, який роздавав довідки.
— Заспокойтеся, громадянко… — почав він. Але стара знову закричала:
— Убивці! — плюнула йому в обличчя і забилася…
Всі мовчали, пригнічені. То тут, то там лунали схлипування і гучний плач…
Я зайшла до своєї квартири, звідки мене вже не будуть гнати міліціонери. Вдома нікого не було, і я могла, не стримуючись, плакати.
Плакати за чоловіком, який загинув у підвалах Лубянки у 37 років, у розквіті сил і таланту; за дітьми, що виросли сиротами з тавром ворогів народу, за померлими з горя батьками, за двадцятьма роками мук, за друзями, які не дожили до реабілітації і яких закопали у мерзлу землю Колими»[1855].