Между тем Медокс побывал в Москве, выклянчил у родных денег и стал пробираться на любимый Кавказ, но был задержан в Екатеринодаре и отправлен в Петербург. Победная реляция о поимке преступника была получена шефом жандармов Бенкендорфом, и тот поспешил уведомить об этом государя. Николай I распорядился упрятать Медокса в один из сибирских батальонов и держать его там под строжайшим надзором.
Пока Медокса везли в Петербург, он снова умудрился бежать, написав по пути письмо сестре, в котором сообщал, что определен рядовым в Омск и что «…дух мой скоро воспрянул — и я на краю пропасти нашел случай писать к государю, который по первой почте отвечал». Медокс находился в бегах, но не унывал и даже «воспрянул духом» от возможности заслужить прощение царя. Казалось, он теперь сам в первом попавшемся на пути городе явится с повинной, но не тут-то было: Медокс, напротив, сменил паспорт, поехал в Одессу и целый год вертелся там среди друзей и родственников сосланных в Сибирь декабристов, не испытывая нужды в средствах.
Из Одессы Роман Михайлович написал еще одно письмо Николаю I (30 мая 1828 года), в котором он излагал историю своих приключений в 1812 году на Кавказе, описывал страдания в тюрьме и просил помиловать его, определив рядовым в Молдавскую армию. Царь отдал новое распоряжение схватить нахала, но тот казался неуловимым: со своими знаниями иностранных языков он легко растворился в многонациональном контингенте портового города. Как бы дразня власти и самого Николая I, «нелегал» Медокс отправил царю еще одно письмо — теперь на хорошем английском языке. Далее в биографии Медокса наступает более чем годичный провал. Аналогичным образом в архивах Третьего отделения по странному совпадению отсутствуют какие бы то ни было сведения о том, что происходило с Медоксом в июле 1828-го — сентябре 1829 года и какие действия в это время предпринимало отделение по его поимке.
После указанного периода Медокс при загадочных обстоятельствах оказался не в Омске, а в Иркутске! Предписание царя сослать Медокса рядовым в Омск все-таки исполнилось, но сосланный повел в Сибири образ жизни отнюдь не простого рядового солдата. Он появляется в Иркутске, заводит тесные связи с наиболее видными декабристами, входит в их дома, пользуется их полным доверием, становится учителем в семье опального городничего А. Н. Муравьева[44], одного из основателей Союза спасения, и даже пытается завести роман с приехавшей в Сибирь его родственницей. Командированные из Петербурга жандармские полковники и ротмистры тайно встречаются в Иркутске с Медоксом, они доставляют от него письма Бенкендорфу и Николаю I. Странные отношения у рядового солдата завязываются с генерал-губернатором А. С. Лавинским, оказывавшим Медоксу тайное покровительство. С бароном П. Л. Шиллингом, агентом Третьего отделения и изобретателем электромагнитного телеграфа, он выезжает в Кяхту, а потом появляется на Петровском заводе.