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

13 февраля Мейтланд отправился в Лондон и Париж, снабженный двумя наборами инструкций. Первый относился к позиции Марии относительно французских религиозных войн после того, как английские войска высадились в Нормандии. Она предложила себя в качестве независимого арбитра. Это был явно неудачный шаг, — хотя возможно, просто дипломатическая хитрость. Елизавета решительно поддерживала гугенотов и на этом этапе не рассматривала вопрос о посредниках, а для Екатерины Медичи война складывалась слишком удачно, чтобы думать о мире.

Второй набор инструкций имел отношение к дебатам в английском парламенте. Если интересы Марии будут ущемлены, Мейтланд должен настаивать на праве выступить и выразить свой протест, чтобы ее претензии были официально зарегистрированы. Вряд ли это была уловка, но парламент в любом случае не стал бы его слушать. Сесил позаботился о том, чтобы в парламент было избрано как можно больше протестантов, а затем предоставил слово своим друзьям. Сэр Ральф Садлер — посланник Генриха VIII, всегда восхищавшийся маленькой Марией, несмотря на то что был обманут ее матерью, теперь обрушился на нее с нападками, которые носили националистический оттенок. «Теперь если эти гордые, нищие шотландцы, — сказал он, — с таким презрением отвергают превосходство Англии… почему мы должны признавать их превосходство или соглашаться на то, что шотландец будет наследником короны нашего государства?»

Последние указания, доставленные Мейтланду в марте курьером, требовали от него вступить в переговоры сначала с Альваресом де Куадра, епископом Аквилы и испанским послом в Лондоне, а затем с родственниками Марии во Франции, предложив брак Марии и дона Карлоса, сына и наследника Филиппа II. Такова была цель Марии. Дона Карлоса очень хотела семья Гизов после смерти Франциска II, но их планам тогда помешала тайная дипломатия Екатерины Медичи. Тогда Мария не проявила никакого интереса к замужеству, потому что собиралась возвращаться в Шотландию. Теперь же она решила возобновить переговоры, заручившись поддержкой Мейтланда, который понимал, что без давления на Англию вряд ли можно заставить Елизавету изменить свое отношение к требованиям Марии. Он также считал Филиппа II религиозным прагматиком, и в основе этой иллюзии лежал общеизвестный факт, что Филипп не одобрял сожжение протестантов при Марии Тюдор, когда был ее мужем. То ли с целью манипулирования, то ли из-за непонимания позиции Филиппа Мейтланд смягчал религиозные вопросы, утверждая, что кальвинисты не будут возражать против дона Карлоса. Он слишком верил, что Филипп, хотя и католик, не был фанатиком, и надеялся, что испанский король и его сын с готовностью примут религиозное status quo, потому что король был «мудрым политическим монархом», который управлял целой агломерацией территорий, находящихся под его властью, «согласно их собственным склонностям».

Мейтланд нанес визит Куадра, который немного позже написал восторженное письмо Филиппу. «Если бы Ваше Величество прислушались к этому, — объяснял он, — то подарили бы своему сыну не только жену таких превосходных качеств… но также дали бы ему власть, которая была бы подобна [всеобщей] монархии». С помощью сына Филипп присоединил бы к своим доминионам все Британские острова и Ирландию. Как видно из этого письма, приманкой с самого начала служили династические претензии Марии — как и боялся Сесил.

Мейтланд вкратце изложил позицию своей королевы. Отказ Елизаветы от встречи требовал от Марии восстановить свою честь и репутацию, стремясь «к такому браку, который позволит ей утвердиться в своих правах».

Де Куадра был польщен и доволен. Он предположил, что Мария попытается выйти замуж за своего деверя, Карла IX. Испанский посол не знал, что Екатерина Медичи категорически отвергала эту идею, и Мейтланд не спешил избавлять его от иллюзий. Наоборот, новый главный советник Марии активно намекал на перспективу второго брака с Валуа, чтобы создать иллюзию конкуренции.

Первый отчет Мейтланда Марии, отправленный из Лондона, рассказывает об убеждении де Куадра, что дон Карлос, которому было почти восемнадцать, «чрезвычайно влюблен» в нее. Второй отчет, написанный месяц спустя из Шенонсо, куда Мейтланд приехал вслед за французским двором, был более мрачным. Он получил известие от кардинала, который прислал резкое письмо, предназначенное для Марии. Знаки были не слишком благоприятными. Ее родственники Гизы, отмечал Мейтланд, не принимают во внимание высказанные желания или чувства Марии. Она интересна им только своим «величием» правящей королевы, из которого они черпают свое «возвышение и уверенность». Другими словами, Гизы помогут племяннице только в том случае, если это будет в их интересах.

Что касается Екатерины Медичи и французских аристократов, то им «почти безразлично, выйдете ли Вы замуж и за кого, при условии, что это не будет угрожать короне». Такая холодная и резкая реакция отражала настроение Екатерины, которая после смерти Франциска II старалась держать Марию на расстоянии. Брак с доном Карлосом, писал Мейтланд, вызывает такое же яростное сопротивление королевы-матери, как и прежде. Ее собственная дочь Елизавета, теперь королева Испании, оставалась бездетной, и, хотя Екатерине была очень нужна помощь Филиппа II в борьбе с гугенотами, она не собиралась преподносить ему на блюдечке права на английский престол.

В Англии, сообщал Мейтланд Марии, существовали «три фракции»: католики, протестанты и сама королева. Елизавета, оставаясь одинокой, хотела устроить брак Марии таким образом, чтобы «не иметь причин для страха». Католики, рупором которых все чаще выступала леди Маргарита Дуглас, графиня Леннокс, настаивали на браке с католиком, чтобы оказать максимальное давление на Елизавету. Протестанты тоже желали, чтобы Мария вступила в брак по религиозным соображениям, но с тем, кто будет защищать протестантство.

Предвидя реакцию шотландских лордов, Мейтланд считал, что «лучшая часть» поддержит Марию, однако найдутся «всякого рода наглецы», в частности союзники Нокса, которые будут яростно выступать против дона Карлоса.

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

Это был не слишком удачный выбор. Эрцгерцог был третьим сыном Фердинанда I, императора Священной Римской империи. В принципе он мог считаться подходящим женихом для шотландской королевы, поскольку слыл умеренным католиком и не фанатиком, но главный его недостаток состоял в том, что он уже числился среди претендентов на руку Елизаветы, а Мария уже отвергла его — как и всех остальных за исключением дона Карлоса.