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