Затем два удивительных предложения сделала Екатерина Медичи: во-первых, Елизавета должна выйти замуж за Карла IX, а во-вторых, Марии следовало стать женой его брата — герцога Анжуйского. Оба предложения были отклонены, однако французский посол Мишель де Кастельно де Мовиссьер был — вполне предсказуемо — очарован Марией, которую он нашел «женщиной в расцвете юности». Елизавета уже отчаялась сдвинуть дело с мертвой точки и писала Сесилу 23 сентября: «Я настолько запуталась, что не знаю, как отвечать шотландской королеве… Придумайте что-нибудь получше, чтобы я могла это включить в инструкции Рэндолфу». Теперь Мария, что для нее нетипично, взяла дело в свои руки и отправила к Елизавете собственного посла, призванного пролить масло на бурные воды. Послом был джентльмен королевской опочивальни сэр Джеймс Мелвилл из Холхилла.

Мелвиллу было двадцать восемь лет; он служил пажом в свите Марии, когда ей было всего шесть лет, потом перешел на службу к коннетаблю Франции Анну де Монморанси, затем — к Казимиру, сыну электора Пфальцского. Мелвилл вернулся в Шотландию 5 мая 1564 года и встречал Марию в Перте, как раз после того она узнала о предложении Елизаветы выйти замуж за лорда Роберта Дадли. Не стоит и упоминать, что Мелвилл был ею очарован: «Я считал, что лучше служить ей за скромное вознаграждение, нежели любому другому государю Европы за огромные деньги». Она послала его в Англию 28 сентября «с инструкциями из уст самой королевы». Записки Мелвилла представляют дословную запись бесед с Елизаветой, но историк Гордон Доналдсон предупреждает, что он, вероятно, сообщает «не то, что они на самом деле говорили, а то, что они потом предпочли считать сказанным».

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

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

Елизавета, продолжая льстить Мелвиллу, показала ему портрет Марии, находившийся в ее личной коллекции миниатюр. Но Мелвилл заметил, что одна из миниатюр завернута в бумагу, на которой рукой Елизаветы было написано: «Портрет моего господина», — то была миниатюра Лестера. Она показала Мелвиллу «большой, размером с теннисный мяч, рубин», и он заметил, что она могла бы отослать его королеве Марии как знак своей любви. После резкого тюдоровского вдоха Елизавета ответила, что если Мария последует ее пожеланиям, то получит и ее рубин, и ее мужчину, но пока что она пошлет ей бриллиант. На следующий день Елизавета поинтересовалась у Мелвилла, которая из них двоих прекраснее, и он ответил, что Елизавета — прекраснейшая королева Англии, а Мария — прекраснейшая королева Шотландии. Елизавета довольно резко потребовала выбрать между ними, и Мелвилл признал, что хотя Мария очень красива, у Елизаветы кожа белее (из-за более чем щедрого употребления ядовитых свинцовых белил). Каковы ее любимые развлечения? Мелвилл теперь отчаянно импровизировал: он сказал Елизавете правду — что Мария только что вернулась с охоты из Хайленда, и солгал — что она любит читать серьезные книги и исторические хроники; правдой было и то, что она также играет на лютне и клавесине. Елизавета тоже гордилась своими музыкальными способностями, поэтому спросила у Мелвилла, хорошо ли играет Мария, и тот дал рискованный ответ, что для королевы она играет совсем неплохо. В тот вечер Мелвилла пригласил на прогулку лорд Хансдон, и тогда — совершенно случайно, конечно! — ему удалось услышать, как Елизавета играет на клавесине. Елизавета позвала Мелвилла к себе и заговорила с ним по-немецки, но ее немецкий был несовершенен, поэтому она перешла на итальянский, на котором Мелвилл не говорил. Таким образом, этот вечерний лингвистический поединок закончился вничью.

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

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

Летингтон и Морей встретились с Рэндолфом и Бедфордом в Бервике, но их встреча ничего не дала. Сесил продолжал настаивать на кандидатуре Лестера, а Мария колебалась. Она просто ждала, когда события вынудят ее к каким-либо действиям, но все происходило очень медленно. С политической точки зрения обе стороны колебались по разным причинам: если бы брак состоялся (а теперь всем уже было ясно, что он состоится), а затем распался бы, никто не захотел бы взять на себя ответственность за это. Летингтону не нравился Лестер, потому что тот был англичанином, а Морею не нравился Дарнли, потому что тот стал бы оказывать покровительство католикам, если бы ему это было выгодно. Оба лорда «обменялись страстными речами».

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