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