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