Трио все еще продолжало борьбу на финансовом фронте, и они были удовлетворены, когда положили в карманы свои первые разумно оплаченные чеки после того, как согласились сыграть альбом, составленный королем немецкого электронного фанк-джаза Эберхардом Шунером в Мюнхене.
10 ноября 1977 года группа вернулась в Лондон после трех недель, проведенных в Германии. Они ожидали, что обнаружат массу новых предложений, но спустя месяц все также не было ни одного выступления, ни одного контракта или записи. Все, чего достигла «Полиция», — это четыре недели неспешных репетиций, во время которых они умудрились значительно улучшить свое исполнение.
Затем последовали еще два месяца репетиций, но абсолютно никаких выступлений. Люди из музыкальной сферы начали спрашивать, что же случилось с «Полицией». «Однажды мы решили надурить всех этих ребят и загрузили наше оборудование в машины и просто убрались», — вспоминает сегодня Стюарт.
Все это время Стинг, подстегнутый появлением в группе Энди, неистово писал музыку: «Я чувствовал постоянное давление. Я все время выходил с новыми песнями».
После того как группа избавилась от своего руководства, она решила записать альбом и выпустить его самостоятельно. Они полагали, что альбом произведет гораздо большее впечатление в коммерческом мире, чем отдельный сингл, и даже рассчитали, что им надо продать пять тысяч экземпляров, чтобы покрыть все издержки. Это казалось реальной целью. Но даже на это у них не нашлось приблизительной суммы (нужно хотя бы покрыть все затраты), и Стюарт пошел к своему брату Майлзу за помощью. Майлз неохотно согласился занять ему достаточно денег, чтобы заплатить студии по счетам. Он колебался не только потому, что не любил выказывать благосклонность своему брату, но еще потому, что он в глубине души «приберегал» эту группу для себя.
Прежде чем они смогли запустить проект, все было приостановлено Рождеством. Стинг, к этому времени проживающий в маленькой подвальной квартирке на Лейнстер-сквер, Бэйсуотер, устраивал новогодний вечер с представлением хай-фай регги из коллекции Стюарта.
В первую неделю января 1978 года Стинг вернулся в Ньюкасл для последнего выступления с «Last Exit», которое происходило в переполненном университетском театре. Это было его первое выступление за два месяца, и он начал размышлять, а не был ли его переезд на юг большой и грубой ошибкой. Затем он посмотрел в лица других членов группы и понял, что ему нужно нечто большее, чем просто находиться среди друзей в группе, катающейся по северо-востоку от выступления к выступлению. Он жаждал звездного небосклона, богатства и чувствовал, что «Полиция» стоит на грани получения всего этого.
В течение недели после возвращения из Ньюкасла Стинг снова вместе с «Полицией» записывал песни для недорогого альбома в студии «Сурри Саунд» в Лезерхеде. Эта студия была оригинальным замыслом Найджела Грея, врача, который оставил свою медицинскую карьеру ради рок-н-ролла. Это было единственное место, которое могла себе позволить снять «Полиция».
Майлз Копленд, хотя официально и не был менеджером, завершил все переговоры со студией от имени группы. Сначала он предложил Найджелу Грею две тысячи фунтов по завершении записи или процент от продаж альбома, если тот готов ждать. Грей остановился на двух тысячах фунтов, но затем потратил много месяцев, пытаясь выжать эти деньги из Майлза.
Группа решила, что альбом должен называться «Outlandos D'Amour» («Заморская любовь»). Иногда Майлз забегал в студию посмотреть на предмет своих инвестиций. В первый раз, когда он приехал в Лезерхед, группа только что завершила композицию «Будь моей девушкой». Майлз ненавидел ее и возмущённо заявил, что это звучит как «Curved Air» пятилетней давности.
Однако в следующий раз Майлза встречали звуками «Роксаны». Он был, можно сказать, потрясен песней, схватил копию записи, обещая использовать ее для того, чтобы обеспечить группе хорошую сделку.
Майлз принес пленку в «А&М Records», где одна из его других групп, «Squeese», уже получила хороший контракт. Копленд убедил их выпустить «Роксану» синглом. У группы поднялось настроение, когда они услышали хорошую новость. Их неприязненное отношение к Майлзу сразу же улетучилось. Даже Стинг признает: «Под руководством Майлза мы совершили нашу первую сделку с записывающей компанией, которая принесла нам материальную свободу. Уж если мы двинулись вперед, нас уже было не остановить».
Сделка, проведенная Майлзом Коплендом, оказалась удачной. Он фактически отдал «А&М Records» этот сингл, не требуя никакого аванса на том основании, что он верит, что продажи будут столь высокими и группа заработает гораздо больше на гонораре. Они в конце концов сделали миллионы только лишь с этой записи! Майлз Копленд предпринял чрезвычайно рискованное дело и доказал, что он великолепный менеджер и умеет прекрасно вести переговоры.
Этот всплеск энтузиазма Майлза вскоре принес им тьму «живых» выступлений. Они поддерживали американскую группу «Spirit» на трех знаменательных для Британии датах в марте того года. Однако Майлз все еще не был официальным продюсером «Полиции». Это был постепенный процесс, и он брал на себя все больше и больше руководящих функций в группе.
Майлз уже создал впечатляющую плеяду успешно выступающих групп, включая «Vishbone Ash», «Renaissance», «The Climax Blues Band» и «А1 Stewart». Однако как раз тремя годами ранее, в 1975 году, возникло неустойчивое положение, и ему пришлось ликвидировать дело. «Тогда я узнал, что достичь вершины не так трудно, как остаться там», — объяснял он позже. «Самой большой западней является то, что у вас есть несколько хитов, и вы думаете, что это навсегда, и позволяете себе расслабиться».
Майлз всегда очень скромничал по поводу того, какую он сыграл роль в старте «Полиции». «Просто случилось так, что я дал им старт. Если бы меня не было там, они все равно бы это сделали».
Наконец-то «Полиция» приобрела лицо и форму. Запись «Outlendos» продолжалась двухдневными рывками на протяжении первой половины 1978 года. Когда люди впервые услышали музыку из альбома, они не сразу восприняли так называемый «белый» регги, который вызвал критику представителей разных кругов музыкальной индустрии. Однако Стинг считал, что ничего такого не сделал, а просто приспособил регги к своим собственным находкам. «В моей голове две формы могли существовать параллельно, и звучало это хорошо. Темп мог внезапно поменяться. Затем, когда мы начали прогрессировать, эти два стиля слились», — пояснял Стинг.
«Роксана» вышла 7 апреля 1978 года и получила благоприятные отзывы. Но ее мало передавали по радио, потому что составители программ неохотно использовали песню о любви к проститутке.
