Петра беспокоила тревожная мысль: не стал ли царевич, ехавший без конвоя, жертвой нападения разбойников, не оказался ли он в качестве заложника у шведов? 9 декабря 1716 года царь поручил генералу Вейде, войска которого дислоцировались в Мекленбурге, отправить несколько отрядов во главе с надежными офицерами для поисков исчезнувшего сына. Одновременно царь вызвал Аврама Веселовского из Вены в Амстердам и 20 декабря вручил ему собственноручное повеление, «что где он проведает сына нашего пребывание, то разведав ему о том подлинно, ехать ему и последовать за ним во все места, и тотчас о том, чрез нарочные стафеты и курьеров, писать к нам; а себя содержать весьма тайно, чтоб он про него не проведал».
Вполне вероятно, что Петр подозревал, что сын бежал в Австрию. Иначе зачем он поручил поиск сына не какому-либо дипломату, представлявшему интересы России в Берлине или Париже, а именно резиденту в Вене? О догадке Петра свидетельствует и его послание к цесарю, которое должен был вручить Аврам Веселовский. Не располагая точными сведениями о том, что сын укрывается во владениях цесаря, Петр в собственноручном письме к Карлу VI извещал об исчезновении сына и деликатно просил, «ежели он в ваших областях обретается тайно или явно, повелеть его с сим нашим резидентом, придав для безопасного проезду несколько человек ваших офицеров, к нам прислать, дабы мы его отечески исправить для его благосостояния могли, чем обяжете нас вечно к своим услугам и приязни».
Между тем в донесениях Вейде отсутствовало что-либо утешительное. Он отправил двух офицеров в Немецкую землю и одного в Польшу. 22 января 1717 года Вейде извещал царя: «Из Бреславля пишет один из посланных, что там в городе был в одном доме и сказывался купцом из русской армии тому назад с девять недель и имеет при себе двух сыновей и единую дочь и поехал, не мешкав, по Венской дороге. Должен быть он». Однако царевича сопровождали не три, а четыре человека, а главное, Евфросинья никак не могла представляться дочерью царевича, равно как и два взрослых человека не могли называться его сыновьями — царевичу шел двадцать седьмой год.
Другие посланцы тоже сообщали не более радостные сведения. Один из них доносил, что имярек был в Гданьске и Кенигсберге, в то время как царевич не доехал до Кенигсберга. Другой сообщил, что беглец провел в Вене одну ночь и скрылся в неизвестном направлении.
Царевич и в самом деле сумел запутать следы. В почтовой карете, выехавшей из Либавы, сидел уже не наследник русского престола, а московский подполковник Кохановский с супругой и поручиком. В другой карете разместились его служители. В пути произошло еще несколько метаморфоз. Подполковник Кохановский стал регистрироваться на почтовых станциях как польский кавалер Кременецкий. Чтобы изменить внешность, он начал отращивать бороду. Наконец, не доезжая Вены, царевич обрядил Евфросинью в мужское платье и стал выдавать ее за офицера.
