Тем не менее во Францию Мата Хари на этот раз все-таки попала. В разговоре с капитаном Ладу в августе 1916 года в Париже она заявила, что плыла на пароходе «Зеландия». Этот пароход отплыл из Голландии 24 мая 1916 года. А 12 июня 1916 года Мата Хари прибыла в Мадрид, откуда два дня спустя отбыла в Париж. 16 июня в пограничном городке Андай ее задержали французы. Французская контрразведка по «наводке» англичан попыталась установить наблюдение за Матой Хари. А затем неожиданно пришло распоряжение вообще не пускать ее во Францию. Артистка была возмущена. Французский чиновник на границе ответил, что и сам не знает причин запрета, и посоветовал ей попросить помощи у голландского консула в Сан-Себастьяне. Разозленная Мата Хари тотчас написала письмо своему старому близкому другу, Жюлю Камбону, бывшему генерал-губернатору Алжира, бывшему французскому послу в Вашингтоне, бывшему французскому послу в Мадриде (там они и познакомились), бывшему французскому послу в Берлине и действующему генеральному секретарю МИД Франции с 1915 года. Его брат Поль в 1898–1920 годах был французским послом в Лондоне. Мата Хари просила своего высокопоставленного друга, чтобы ее все-таки пустили во Францию. Если бы она действительно была шпионкой, сам факт запрета въезда в Англию и во Францию должен был бы заставить ее насторожиться и заподозрить, что контрразведка стран Антанты ее раскрыла. Но никакой тревоги в письмах Маты Хари нет, одно возмущение. Общение с немцами как до, так и во время войны никогда не казалось ей криминалом. Ведь она была подданной нейтральной Голландии и никаких обязательств в отношении Франции не имела. Ее капризное и непредсказуемое поведение делало ее плохим агентом в глазах руководителей любой разведки мира, и им вряд ли пришло бы в голову пытаться ее завербовать, хотя и во Франции, и в Германии у нее было много высокопоставленных знакомых. Кому нужен агент, чье поведение непредсказуемо и который в случае чего наверняка будет работать только на себя? Лео Фауст, который в годы Первой мировой войны был корреспондентом голландских газет в Париже и неоднократно встречался с Матой Хари, писал о ней в 1959 году Сэму Ваагенаару: «Все эти годы во мне росла убежденность, что никакой шпионкой она не была. Ей это просто не было нужно, потому что она могла получать достаточно денег совсем другим путем. Кроме того, она была слишком глупа, чтобы хоть кто-то нашел ее подходящей для шпионской работы. Напротив, такого человека следовало бы рассматривать как опасность для самого себя, если доверить ей какую-либо тайну».

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

Ладу послал для слежки за Матой Хари двух агентов, которые наблюдали за ней несколько месяцев днем и ночью. Составленное на основе их донесений досье регистрирует почти всех ее посетителей с 18 июня 1916 года по 13 января 1917 года, ее телефонные звонки, всех, с кем она переписывалась, а также покупки и поездки.

Во время Первой мировой войны голландская подданная Маргарета Зелле могла ездить из Франции на родину и обратно только через Испанию и Англию.

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

Из Парижа Мата Хари направилась в Испанию. Во время поездки она будто бы наблюдала на железнодорожных узлах Центральной и Южной Франции за перемещением военных эшелонов и за скоплениями войск. 11 января 1916 года Мата Хари достигла франко-испанской пограничной станции Андай и через сутки прибыла в Мадрид. Там она остановилась в «Палас-отеле» и связалась с военным атташе германского посольства, майором Калле, чтобы передать информацию о том, что она видела и слышала во время путешествия. Эта информация, видимо, показалась майору настолько важной, что он распорядился немедленно передать ее консулу Крамеру в Амстердам. Радиограмма, как всегда, была зашифрована кодом министерства иностранных дел. Но этот код читали британские дешифровщики.

После Испании Мата Хари через Португалию вернулась в Гаагу, где встретилась с бароном ван дер Капелленом. 15 мая 1916 года она получила паспорт, а вскоре – и въездную визу во Францию. Но британское консульство отказало ей в визе для краткосрочного пребывания в Англии. На запрос нидерландского МИД из Лондона по телеграфу ответили, что у «Форин офис» есть свои причины, по которым пребывание Маргареты Зелле в Англии нежелательно. Тогда Мата Хари решает ехать во Францию, но не через Англию, а через Испанию. 24 мая 1916 года она села в Гааге на пароход «Зеландия» до испанского порта Виго. 16 июня через пограничную станцию Андай она попыталась въехать во Францию. Но французские пограничники, несмотря на ее энергичный протест, отказались пропустить ее. Тогда Мата Хари написала письмо своему старому другу Жюлю Камбону, генеральному секретарю французского МИД. Но уже на следующий день, еще до отправки письма, она узнала, что может беспрепятственно въехать во Францию.

В Париже Мата Хари вновь сошлась со своим давним любовником Жаном Аллором. Он был лейтенантом кавалерии. После тяжелого ранения он стал служащим в военном министерстве.

В 1916 году у французской контрразведки появились первые подозрения на ее причастность к работе на Германию. Узнав об этом, Мата Хари сама явилась во французские спецслужбы и предложила свои услуги французам, случайно назвав, между прочим, имя одного из своих любовников, хорошо известного ее собеседникам в качестве немецкого агента-вербовщика. Капитан Ладу из контрразведки ее перевербовал. Французская разведка отправила ее в начале 1917 года с миссией в Мадрид, и подозрения в шпионаже, по заявлению французских контрразведчиков, окончательно подтвердились: был перехвачен радиообмен немецкого агента в Мадриде с центром, где тот указал, что перевербованный французами агент Х-21 прибыл в Испанию и получил от немецкой резидентуры указание вернуться в Париж. Есть версия, что радиоперехват был специально рассекречен немцами, чтобы избавиться от двойного агента, но она кажется маловероятной.

В Париже Мата Хари познакомилась со штабс-капитаном 1-го Особого полка 1-й Особой бригады Русского экспедиционного корпуса во Франции Вадимом Павловичем Масловым. Она даже утверждала, что влюбилась в него сильнее, чем в какого-либо иного мужчину за всю свою жизнь. Когда шесть месяцев спустя ее арестовали в Париже, в ее комнате нашли разные фотографии Вадима и его визитную карточку (визитные карточки Мата Хари собирала и хранила всю свою недолгую жизнь). На одной из фотографий, хранящейся в архиве французских спецслужб, есть собственноручная надпись Маты Хари: «Виттель, 1916 – воспоминание об одних из самых чудесных дней моей жизни, проведенных с моим Вадимом, которого я люблю больше всего на свете». Интересно, что позднее из-за ранения Маслов одно время носил повязку на глазу. И эту повязку Мата Хари старательно пририсовала на фотографии чернилами.