Судя по всему, Вильгельм не был искусным дипломатом и не отличался особой дальновидностью. Как мы уже видели, король очень дорожил своим альянсом с Фландрией, ведь ввиду угрозы со стороны викингов этот союз имел немаловажное значение для безопасности Англии. Вильгельм даже платил графу денежный феод — 200 фунтов в год. Однако в 1071 г. случилось так, что либо герцог совершил грубую ошибку, либо позволил себя обмануть. Когда в 1070 г. умер Балдуин VI, граф Эно и Фландрии, брат королевы Матильды и родственник Филиппа I Французского, его наследник Арнульф III был еще слишком юн, поэтому власть оставалась в руках вдовы графа — Рихильды Эгисгеймской. За короткое время она утратила всякую популярность, и во Фландрию вторгся дядя мальчика — Роберт Фриз. Чтобы помочь Матильде справиться с этой проблемой, Вильгельм послал в Нормандию Гильома Фиц-Осборна, эрла Герефордского, и когда Филипп собрал армию, чтобы восстановить в правах изгнанников, эрл присоединился к королю с отрядом, в который входило десять рыцарей. Если, как полагает Ордерик Виталий, эрл Герефордский думал, что во Фландрии ему предстоит легкая прогулка, то он, к сожалению, заблуждался, так как 20 февраля 1071 г. Роберт Фриз напал на королевскую армию у Бавеншова близ Касселя, обратил в бегство Филиппа, взял в плен Рихильду и убил Арнульфа. В бою погиб и Гильом Фиц-Осборн. Тело эрла отвезли в Нормандию для захоронения в стенах монастыря, основанного им в городе Кормейле.
Вскоре после битвы Роберт Фриз и король Филипп заключили мир. Новым графом Фландрским стал брат Матильды, но Вильгельм, видимо, был оскорблен убийством своего сенешаля и друга в битве при Касселе, поэтому в отношениях между двумя дворами никакой приязни впоследствии не наблюдалось. Кроме того, Роберт, который проявлял интерес прежде всего к своим имперским фьефам и стремился распространить свою власть на восток, предпочитал доверять защиту Фландрии своему сюзерену — королю Франции, а не своему зятю — герцогу Нормандскому. Союз графа и французского короля был скреплен браком между Филиппом и падчерицей Роберта — Бертой Голландской, а свое враждебное отношение к Вильгельму граф открыто выразил тем, что выдал свою старшую дочь замуж за Кнута II Датского, претендента на английский престол. Ситуация напоминала недавнее прошлое, а именно 1075 г., когда датскому флоту перед вторжением в Англию было разрешено стать на якорь у берегов Фландрии.
В начале 1072 г. Вильгельму удалось все же выкроить время, чтобы посетить Нормандию впервые после 1067 г., и, скорее всего, его сопровождал Одо Байеский. Он созвал всех своих баронов из герцогства и из графства Мэн, принял от них оммаж, а затем вернулся в Англию, чтобы вторгнуться в Шотландию. В начале 1073 г. Вильгельм, освободившись наконец от бремени наиболее насущных английских проблем, снова возвратился в Нормандию, чтобы усмирить беспорядки в Мэне. Нормандская власть в графстве не пользовалась популярностью, и это создавало благоприятную почву для заговоров. Влиятельные бароны, такие как Жоффруа Майеннский, плели интриги в своих интересах, а жители Ле-Мана решили создать коммуну. Всеобщее настроение склонялось в пользу того, чтобы правителем снова стал какой-нибудь местный граф, но в последний момент политическая необходимость вынудила мятежников обратиться к графу Анжуйскому. В период между 1068 и 1072 гг. Герзента, сестра Гуго IV, последнего графа Мэнского, вместе с мужем Адзо II, маркизом д'Эсте в Венеции, заявили о правах своего младшего сына. Однако в 1072 г. Жоффруа Анжуйский воспользовался беспорядками и овладел Ле-Маном. В начале следующего года Вильгельм выступил в Мэн с большой англо-нормандской армией и довольно легко подавил этот неприкрытый мятеж. Однако поскольку и Анжу, и Франция, а иногда и Бретань занимали враждебную позицию, власть Вильгельма над Мэном пошатнулась, и до конца его правления это графство постоянно становилось очагом заговоров и мятежей, поддерживаемых и подстрекаемых графом Анжуйским.
Филипп Французский стремился любыми способами досадить Вильгельму. В 1074 г. из Фландрии в Шотландию вернулся Эдгар Этелинг и был с почестями принят своим зятем, Малькольмом. Однако Малькольм не был готов его приютить, поэтому порешили на том, что принц примет предложение Филиппа укрыться в Монтрейском замке, расположенном на границе между графствами Булонь и Понтье. Эдгар отправился во Францию, но из-за шторма вынужден был вернуться в Шотландию, и на этот раз Малькольм посоветовал ему заключить с Вильгельмом мир. Принц проехал через всю Англию и отплыл в Нормандию. Король принял его весьма учтиво, и Эдгар оставался с ним до 1086 г., когда решил попытать счастья в Апулии. Кстати, в этом же году его сестра Кристина постриглась в монахини в аббатстве Ромси.