В 1869 году Запольский, раздобыв себе «надёжный паспорт», вместе с женою и дочерью скрылся из Тоболь-ска. Объявились они в Новгородской губернии, в Тихвине, откуда происходили его предки. Здесь его, родившегося в Питере, конечно же, никто не знал, поэтому он поселился вместе с семьёю в городе: завёл торговлю, познакомился с обывателями — словом, зажил обычной жизнью. Так проходит два спокойных года, и в 1871 году он сумел даже оказаться причисленным к мещанскому сословию Тихвина. Это давало ему статус, возвращало права, придавало устойчивость его положению. Но «вспыльчивость натуры» не могла не проявиться, и он опять оказался под стражей — за нанесение оскорблений товарищу прокурора и полицейскому чиновнику. В тюрьме открылось, что он сбежал из Сибири, и его вновь вернули «в не столь отдалённые места», приписав к городовым крестьянам Тобольска. Жить в Сибири Запольскому было уже невмоготу, и он, сведя знакомство с волостным писарем, сумел склонить того к подлогу — выписать ему паспорт на имя Запольского, сроком на год. Получив документ, он бросил жену и дочь в Тобольске, а сам вернулся в Россию. В Сибирь он никогда не вернётся, как не увидит ни жены (она умрёт в 1876 году), ни дочери, оставшейся жить в Тобольске.
Сбежав в очередной раз, в 1872 году Запольский добрался до Одессы, где устроился на службу не куда-нибудь, а в полицию, на должность писца. Пробыл он здесь недолго, но успел подделать на официальном бланке крайне важный для него документ — «копию» с вымышленного им постановления Государственного совета «о возвращении военному врачу Запольскому прав, чинов, орденов». Так Андрей Аполлонович впервые объявил себя врачом. Недрогнувшей рукой он подписал эту филькину грамоту титулом и личным автографом государя императора, самодержца всероссийского. На этом же «шедевре криминального творчества» была сделана нахальная приписка: «Запольскому, по прибытии в Петербург, надлежит незамедлительно явиться для представления Государю лично». На провинциальных чиновников эта опереточная «царёва грамота» действовала умопомрачающе, когда Заполь— ский, облачённый в мундир военного врача, являлся к ним.
Разъезжая по городам и весям, он пользовался этим документом, требуя немедленно выдать денег «на дорогу до Петербурга». Ему нигде не отказывали. Предъявив в одной типографии все то же «постановление Государственного совета» и подложное удостоверение от генерал-губернатора Восточной Сибири Хрущёва, он заказал бланки, которыми пользовался в дальнейшем для своих мошеннических операций.
Скрывшись в 1877 году из Киева, Запольский, словно змея, решил «сбросить старую кожу». На свет появился «доктор Черемшанский». Андрей Аполлонович заготовил себе целый комплект копий различных бумаг на эту фамилию. Черемшанским он назвался отнюдь не случайно. Существовали целых три настоящих врача, носившие эту фамилию: отец служил в Сибири, а два сына Черемшанских практиковали в Петербурге.
Обретя новую фамилию, беглец прежде всего отправился в Москву. По дороге он свёл знакомство с кандидатом на военно-судебные должности Владиславлевым, от которого узнал адреса знакомых тому семейств Дяковских и Ефимовых. Явившись в дом Ефимовых, он отрекомендовался военным доктором и передал хозяевам поклон от Владиславлевых. Здесь же на квартире у Ефимовых, где он был принят как добрый друг, он познакомился с их прия-тельницей, «девицей на выданье» Анной Коробовой. «Доктору» позарез нужна была «база в Москве», и он решил обеспечить её проверенным способом, через женитьбу. После короткой осады девицы он, уже через два дня знакомства, просил руки дочери у матери Коробовой. Напуганная таким натиском мамаша поначалу отказала, но опытный обольститель «повёл правильную осаду». Все это время он «выезжал на гастроли в провинцию», объясняя свои отлучки «срочными служебными командировками».
Наконец, 13 февраля 1878 года он обвенчался — четвёртый раз в своей жизни. Для этого ему пришлось изготовить целую серию фальшивых бумаг, необходимых для представления «по брачным обыскам». Мошенник создал удо-стоверение от МВД, Медицинского департамента и от нового генерал-губернатора столь памятной ему Восточной Сибири, генерала Редерихса. От последней инстанции было выписано разрешение на имя военного врача Андрея Аполлоновича Черемшанского, 51 года, реформаторского вероисповедания, командированного старшим врачом на Сахалин, которому, как вдовцу, дозволялось вступить в третий брак.