Когда на следующий год Вильгельм Завоеватель вернулся в Нормандию, Эдгар, Эдвин и Моркер отправились вместе с ним. Впрочем, к весне Эдгар бежал и — возможно, после неудачной попытки поднять восстание — сел на корабль со своей матерью, Агатой Венгерской, и двумя сестрами, Маргаритой и Христиной, намереваясь вернуться в Венгрию. Встречный ветер отнес их корабль в Северное море. Они доплыли до Ферт-оф-Форта и высадились в заливе св. Маргариты, близ Данфермлайна, фактической столицы Малькольма. Там их принял шотландский король и предоставил им убежище. Маргарита была уже взрослой девушкой, отличавшейся необыкновенной красотой, обаянием и умом. Сначала она воспитывалась при дворе св. Стефана, где и познакомилась с византийскими традициями, а затем при дворе св. Эдуарда, все еще поддерживавшем тесные отношения с новым интеллектуальным центром Западной Европы — клюнийской Нормандией. Маргарита выросла мудрой, ученой и святой. Королева Ингеборга умерла, и овдовевший Малькольм тут же влюбился в эту странствующую принцессу. Сначала она отказала ему: она и ее сестра должны были постричься в монахини. Со временем она переменила свое решение, но это произошло только через один или два года.
События того времени носили бурный и не всегда понятный характер. В 1069 г. Вильгельм начал закрепляться на севере Англии, где сильны были легитимистские настроения. Он послал Роберта де Комина (его потомки будут носить в Шотландии имя Коминов) захватить Нортумберленд и Йорк, и из 700 человек, отправившихся с Комином, в живых остался только один. Эдгар присоединился к восставшим, но мятеж был подавлен, а Йорк в наказание был разграблен норманнами. Эдгар предпринял новую попытку, заручившись поддержкой датского флота, и приступом взял Йорк. Однако Вильгельм откупился от датского адмирала и принялся опустошать всю Северную Англию. По всей видимости, Малькольм действовал на стороне Эдгара: он вступил на английскую территорию, обнаружил, что английские легитимисты уже разгромлены, и дошел до Вермута только для того, чтобы убедиться, что сам Эдгар со своей семьей и вождем своих сторонников уже сели на корабль. Согласно Симеону Дюргемскому, Эдгар принес Малькольму вассальную клятву в качестве короля Англии в обмен на предоставленное убежище… А Малькольм получил известие, что Вильгельм передал Нортумберленд, на который он претендовал по праву племянника Сиварда, его кузену Коспатрику, сыну Мальдреда, младшего брата Дункана I, от дочери Ухтреда, ярла Нортумберлендского. И Коспатрик, который поддерживал Эдгара и которого в своем королевстве недавно укрывал от короля Вильгельма Малькольм, начал опустошать Камберленд, на который также претендовал Малькольм. Шотландский король выступил против Коспатрика, разграбил его главную резиденцию в Бамборо и увел в Шотландию так много английских пленников, что, по словам одного английского хрониста, английские рабы появились в каждом шотландском доме. Это был странный способ сватовства к английской принцессе, но в том же 1070 г. Маргарита вышла замуж за Малькольма, и хотя, возможно, она сделала это против своей воли, их брак оказался очень счастливым.
В следующем, 1071 г. Вильгельм двинулся на север, чтобы отомстить шотландцам. Однако Англо-Саксонская Хроника отмечает, что «он не нашел там ничего, над чем он мог бы владеть», ибо из-за постоянных нашествий саксов, датчан, норманнов и шотландцев несчастная Нортумбрия превратилась в выжженную пустыню. Эдгар даже не попытался оказать Вильгельму сопротивление и бежал во Фландрию. Вильгельм дошел до Файфа, но Малькольм, очевидно, больше не видел никаких оснований ввергать свою страну в новую войну ради шурина, позорно отказавшегося от шотландской поддержки. Он встретился с Вильгельмом в Абернети, где они договорились об условиях мирного договора. Вильгельм согласился выплачивать Малькольму ежегодную субсидию и отдать ему двенадцать английских поместий, которые тот должен был, конечно же, держать в качестве фьефов английской короны. Со своей стороны, Малькольм отослал в заложники своего сына Дункана, тем самым гарантируя выполнение условий соглашения. Из этого договора английские историки в очередной раз извлекли различные домыслы о завоевании Шотландии, однако такая ситуация, когда один государь владел землями в другом королевстве и приносил за них оммаж другому королю, была совершенно обычной для феодальной политики. Сам Вильгельм и все английские короли на протяжении столетий были вассалами французской короны в отношении областей, которыми они владели во Франции, но это не означало сюзеренитета Франции над Англией. Если бы Малькольм стал вассалом Вильгельма в отношении Шотландии, он наверняка призывался бы для несения обычной феодальной службы во время различных последующих войн. Положение вассала у Вильгельма вовсе не означало синекуры. Но шотландская армия никогда не сражалась на его стороне.
Мир дал обоим королям возможность успокоить свои страны. В следующем году Эдгар вернулся в Шотландию с известием, что король Франции предложил ему Монтрей на нормандской границе. Малькольм посоветовал ему принять предложение и обосноваться там, очень щедро наделил Эдгара и его свиту золотой и серебряной посудой, королевскими пурпурными мантиями, подбитыми горностаем, и отправил в плавание, но… через некоторое время они снова явились к его двору, потерпев кораблекрушение. Теперь Малькольм хорошо знал Эдгара, он уже встречался с Вильгельмом и свел личную дружбу с его сыном Робертом. Шотландский король отказался нарушить мир ради беспомощного Эдгара и посоветовал тому покориться. Эдгар послушался и принес Вильгельму клятву верности, за что и получил во владение замок в Нормандии.
Затем начались домашние междоусобицы. Маелснехтайн, сын Лулаха, вырос и, вероятно, заявил о своих притязаниях либо на шотландский трон, либо на звание мормаора Морея, принадлежавшее его деду Гиллекомгану. Во всяком случае, в 1077 г. Малькольму пришлось с ним сразиться. Король выиграл кампанию, однако Маелснехтайну была сохранена жизнь и он дожил до 1085 г. В 1079 г. под угрозой оказался шотландско-английский мир. Вильгельм вступил в Нормандии в войну со своим старшим сыном Робертом, другом Малькольма, а в ответ Малькольм вторгся в Англию. Очевидно, его приветствовала Нортумбрия: во всяком случае, в следующем году Вильгельм направил опустошать эту провинцию епископа Байе. Роберта, с которым Вильгельм уже примирился, он послал грабить Шотландию. Однако тому, по-видимому, претило разорять владения своего друга. Он дошел до Фолкерка, а затем развернулся и двинулся обратно. Впрочем, он построил Ньюкасл на реке Тайн в качестве пограничной крепости вместо утерянного Эдинбурга, тем самым достигнув компромисса между дружбой и сыновьими обязанностями. После этого между Англией и Шотландией вновь воцарился мир, длившийся 14 лет и нарушенный только после смерти Вильгельма. Разразившаяся война оказалась роковой для Малкольма и его супруги.
В эту эпоху перманентных войн происходило множество событий иного порядка. В Шотландию проникли новые представления, новые идеалы, а Малькольм и Маргарита всячески их поддерживали. Они были счастливы в браке. Суровая агиография, повествующая об их жизни, полна мелких подробностей, раскрывающих перед нами их взаимоотношения: в юности Малькольм, раздираемый ревностью, вызванной удалениями его жены в лесную пещеру, последовал за ней, нашел ее преклонившей колени в страстной молитве за него и в раскаянии упал к ее ногам. Маргарита, раздав все свои деньги нищим, взяла деньги из кармана мужа, но была замечена за этим проступком; в ответ Малькольм взял ее любимые книги и возвратил их ей в золотых переплетах с драгоценными камнями. Эти рассказы не подразумевают модного сегодня образа суровой и набожной классной дамы, принуждающей бедного Малькольма подчиняться чужеземным обычаям. В действительности, судя по тому, что нам известно об этом короле, плохо пришлось бы той жене, которая попыталась бы вести себя таким образом. А мы знаем, что их союз был прочным. Королева не могла удержать его от войны с Англией, — может быть, живя в то время, она даже не думала об этом, ибо английские короли, против которых воевал ее супруг, узурпировали права ее брата. Но она сумела стать товарищем и соратником мужа в других сферах его деятельности. Оба они во времена своей молодости познакомились с новыми стандартами развивающейся французской цивилизации, которые св. Эдуард перенес из Руана в Вестминстер. Они приняли их. Шотландский двор теперь приобрел не только внешние блеск и лоск, но и новые представления о морали. В ее основе была чистая, достойная и нежная семейная жизнь, основанная на постоянной религиозной практике, и рука об руку с придворным великолепием шла широкая и целенаправленная забота о бедняках. Это сочетание характерно для того времени: король, королева и придворные одевались в прекрасные заморские одеяния, а купцы постоянно привозили новые моды, и всё же все они ревностно соблюдали посты и непрестанно молились, и ни одному нищему не приходилось напрасно умолять о помощи. Не случайно королевство ее мужа канонизировало королеву Маргариту еще до того, как это сделал Папа.