Постепенно Менезий и Гордон обжились в Москве, втянулись в службу, стали принимать участие в местных забавах — так, Гордон в июне 1662 года выиграл на скачках, сорвав куш в изрядную по тем временам сумму 100 рублей, которые, впрочем, почти целиком ушли на угощения и пиры для тех, кто приходил поздравить его с удачей.

Упоминание о скачках, сделанное в дневнике Гордона, открывает нам неожиданную сторону московской жизни той поры — даже в Париже, при дворе французских королей, первые скачки на призы состоялись 23 февраля 1689 года. Судя же по записи в дневнике Гордона, в Москве скачки проводились за двадцать шесть лет до этого, а вероятно, и того раньше, поскольку Стальное Запястье упоминает о них как о деле вполне обычном, в котором он просто принял участие и выиграл.

Среди приятелей, приобретенных Гордоном и Менезием в Москве, был шотландец Айвен Аннанд, который прежде служил в армии и даже имел чин капитана, но предпочел оставить службу ради более выгодных занятий медициной в русской столице. Свели их весьма прискорбные обстоятельства: как-то раз, зайдя в гости к Менезию, Гордон излишне приналег на вареную щуку и водку, переел и расхворался. Для пользы лечения с полковой квартиры Гордона перевезли в Немецкую слободу, в дом полковника Снивенса, где его окружили заботами семейство Кроуфорд и хирург Аннанд, взваливший на себя обязанности врачевания.

Мистер Аннанд, как и другие московские знакомые шотландцев, уже давно жившие в Москве, без устали твердил Гордону и Менезию, которые считались завидными женихами, что им пора жениться.

В Немецкой слободе брачные интриги были одним из самых ярких и насыщенных эмоциями развлечений. Окрутить вновь прибывших на жительство в слободу холостяков было своего рода спортом, многодневным действом, за ходом которого следили десятки заинтересованных глаз. Созерцатели делились на партии, каждая из которых «болела» за свою кандидатку в супруги, всячески стараясь ей помочь «устроить судьбу». Тайно принимались даже ставки на то, кто из претенденток сумеет увести под венец очередной объект брачной охоты.

Первым из двух друзей-шотландцев капитулировал осажденный сватами Павел Менезий, который женился в 1662 году. Вслед за ним стал склоняться к мысли о законном браке и Гордон, решивший подобрать себе суженую из офицерских дочерей, справедливо полагая, что люди одного с ним сословия и примерно равных доходов охотнее его примут. Перебрав несколько кандидатур, он остановился на Катарине Бокховен — дочери Филиппа Альберта ван Бокховена, который вместе с отцом и братом, как мы помним, прибыл в Москву еще при царе Михаиле, обжился и осел здесь, похоже, навсегда.

С будущей невестой Гордона свел Аннанд. Отец девицы в это время пребывал в плену у поляков, попав туда в ходе той же кампании, что и полковник Кроуфорд. Его брат Корнелиус ван Бокховен тоже угодил в плен, но ему удалось освободиться при посредничестве посла Леонтьева, как Кроуфорду и многим другим. В 1662 году Корнелиус уже был в Москве.

То, что Катарине было всего тринадцать лет, Гордона совершенно не смущало — девушка она была крепкого сложения, рослая и вполне уже созревшая. Он явился в дом Корнелиуса Бокховена и, застав предмет своего интереса в одиночестве, с прямотой шотландца, недаром носившего прозвище Стальное Запястье, изъяснил свой интерес. Девушка ответила, что целиком полагается на волю своей благодетельной матушки, а потому как та скажет, так она и поступит.

С тем они и распрощались. Случай переговорить с будущей тещей Патрику представился уже на другой день: у Катарины ван Бокховен был день рождения, и, будучи приглашен на торжество вместе с Айвеном Аннандом, Патрик Гордон, купив в подарок дамские перчатки, ленты, еще кое-чего по мелочи, все это поднес виновнице торжества. Тут же, не откладывая дела, он объявил мамаше своей избранницы, что намерен просить руки Катарины.

Пребывая в некотором смятении чувств, госпожа Бокховен кликнула свояка, и явившийся на зов Корнелиус заявил, что при живом отце, без его согласия, решать брак дочери совершенно невозможно. Решили ждать возвращения Филиппа Альберта ван Бокховена, договорившись, что майора станут принимать в доме как жениха, а Катарина без него или его согласия не будет посещать свадьбы, балы и другие увеселения.

Меж тем служба Гордона и Менезия шла своим чередом — оба побывали с войсками на Украине, участвовали в осаде Риги и в других боевых делах, в которых отличились, за что в 1663 году оба получили повышения — Гордон стал подполковником, а Менезий майором.

Долгое ожидание свадьбы тяготило Гордона, и он предпринял усилия, чтобы ускорить возвращение потенциального тестя. Место его содержания было известно, и Гордон, вступив с Филиппом ван Бокховеном в переписку, несколько раз посылал ему денег. Тем временем поляки объявили, что готовы разменять Бокховена на своих, но, понимая, сколь важная фигура находится у них в руках, они желали получить за него большую группу польских пленников. Переговоры тянулись более года, наконец на исходе 1664 года пленные поляки по согласованному списку были собраны в Смоленске. Но ни брат пленника, ни Гордон, занятые делами службы в Москве, выехать на место, чтобы проконтролировать обмен, не смогли, и поляки, назначенные за Бокховена, были обменяны на других людей. После срыва обмена госпожа ван Бокховен, которая уже привыкла смотреть на Патрика как на зятя, написала мужу письмо, прося его дозволения на брак дочери с Гордоном.

13 января 1665 года, ровно через два года после сделанного предложения, дело наконец решилось. Госпожа Бокховен объявила, что согласна выдать Катарину за Патрика, если обряд венчания пройдет по реформаторскому обряду. Скрепя сердце католик Гордон согласился и на это — спорить было бесполезно, да и что бы он мог предложить взамен: ехать венчаться по католическому обряду в Польшу? Таким образом, свадьба подполковника Гордона и девицы Катарины, дочери полковника ван Бокховена, состоялась 26 января 1665 года, а спустя десять месяцев у них уже родилась дочь, нареченная Екатериной-Елизаветой.

В 1666 году подполковника Гордона отправили в Англию, с поручением к королю Карлу II. Он был принят милостиво и, исполнив порученное, не упустил возможности устроить дело семейного свойства: сэр Патрик попросил английского короля ходатайствовать перед польским королем об освобождении его тестя. Этот шаг мог обернуться международным скандалом и перечеркнуть его карьеру, но риск себя оправдал, и в результате давно тянувшееся дело было благополучно разрешено.

Голландец Бокховен, состоявший на русской службе, казалось, никоим образом не мог вызвать сочувствие Карла II, однако русский посланник сумел повернуть дело так, что в Польшу было отправлено письмо, адресованное польскому королю, в котором английский монарх просил освободить состоявшего на русской службе полковника Бокховена. Основанием для просьбы послужило заверение, что пленник является природным англичанином, долгие годы служившим британской короне, но «во время последнего мятежа» (имелась в виду английская революция) он, как и многие другие, вынужден был покинуть страну и в поисках лучшей доли оказался в Москве, где поступил на русскую службу. И вот король Карл просил польского короля «о братской услуге»: распорядиться, чтобы господина Бокховена отпустили и дали возможность вернуться в Англию, где теперь, после реставрации королевской власти, ему уже ничто не угрожает. Эта уловка сработала, и в 1667 году Филипп Альберт ван Бокховен получил свободу, но, как и можно было ожидать, в Англию не поехал, а направился прямиком в Москву, где ждали его жена, дочь, зять и внучка. После его возвращения военная карьера Гордона в России пошла еще успешнее.