Благодаря песням «Last Exit», которые он позже переработал для «Полиции», включая «Постель слишком широка без тебя» и «Так одиноко», которая начала свою жизнь как песня «Exit» «Влюбленный дурак», есть ключи к разгадке музыкального «таинства» и желаний Стинга. Стоит упомянуть несколько художественных произведений, повлиявших на Стинга в 1976 году, поскольку они обеспечивают понимание его сдержанного, «темного» чувства юмора. Судьба казненного американского убийцы Гэри Гилмора, книга «Лолита», которую Стинг прочел по крайней мере три раза, и поэма Теда Хьюга под названием «Правда убивает всех» имели глубочайшее воздействие на него. Он также очень интересовался игрой на классической испанской гитаре и платил гитаристу «Last Exit» Терри Эллису по пять фунтов в час, чтобы тот его учил.
Тем временем «Last Exit» была близка к тому, что наконец-то станет известной. Кэрол Уилсон из «Virgin Music Publishing» так понравилась группа, что она убедила целый батальон сотрудников компании, включая самого босса Ричарда Брэнсона, приехать в Ньюкасл и посмотреть, как группа поддерживает Алана Прайса в Сити-Холле. К сожалению, это было ужасное выступление, потому что группа не проверила как положено звук и не смогла установить необходимое количество микрофонов на ударных и поэтому звук был любительским.
Ограниченный контингент «Virgin» покинул Ньюкасл, не выразив восторга, но Кэрол Уилсон все-таки попросила «Last Exit» приехать в Лондон и записать несколько дорожек в студии. Ронни Пирсон говорил: «Мы наняли автофургон. Вел его я. Мы отъехали на десять миль от Дурхэма, и фургон поломался».
На помощь пришла АА (Автомобильная ассоциация), и в конце концов группа оказалась в дешевом отеле в Пэддингтоне, в Западном Лондоне, в самом центре района «красных фонарей» столицы. Компания грамзаписи сообщила, что за отель им придется заплатить самим.
«Last Exit» записала одиннадцать дорожек за один день в «Студии Пасвей» от имени «Virgin Records». Это было рекордным достижением за столь короткий промежуток времени. Однако из-за прохладного отношения «Virgin» группа не строила особенных иллюзий. Ронни Пирсон объясняет: «Мы все проделали сами от начала до конца. Никто из «Virgin» даже не потрудился показаться.
Затем «Virgin» притащила всех членов «Last Exit» на встречу в свой лондонский офис: «Вам придется приехать сюда и жить тут. Мы найдем вам жилье»».
Ронни был потрясен: «Я не мог смириться с этой мыслью. Мы говорили им, что всегда сможем прилететь или добраться поездом или доехать как-то еще. У нас не было причин перебираться в Лондон. По крайней мере, я так думал».
Тем не менее, «Virgin» все-таки предложила Стингу сделку, покупая права на его готовые композиции и на все, что он планировал написать в будущем. Фрэнсис была первой, кто прочитал контракт с «Virgin», когда он пришел по почте, в крошечной квартирке, куда она и Стинг переехали после свадьбы. Она утверждает, что никто из них двоих в полной мере не понял его значения, но, во всяком случае, они его подписали.
Стинг утверждает, что он не понял сути своего контракта, согласившись с размером авторского гонорара в 50 процентов при пяти годовых опционах. Он не обратил внимания на некоторые формулировки контракта, «незаметные» или малопонятные фразы в разговоре. Позже Стинг объяснял: «Я думал, что это означает «взаимные опционы», что у меня столько же свободы выйти, как и у них. В этом была моя глупость. Это не было такой уж большой сделкой, но я был взволнован тем, что совершил ее. Я думал: «Я настоящий композитор, автор песен». Это было как приз, это было подтверждением того, что я композитор-песенник. Я мог говорить людям о своих продюсерах. Для меня это был новый уровень, и я испытывал незнакомый трепет».
Стинг был на 50 процентах, тогда как многие крупные композиторы песен и исполнители имели 80–90 процентов. Это был контракт, который будет преследовать Стинга в течение многих лет и приведет к горькой вражде между певцом и знаменитым продюсером Ричардом Брэнсоном.
Однако в то время Стинг и другие члены «Last Exit» были просто довольны, ведь успех, кажется, замаячил на горизонте. Кэрол Уилсон устроила группе рекламное выступление в клубе «Дингу-оллз» в Лондоне, и они получили хорошие отзывы в музыкальной прессе. «Virgin» дала им больше времени на запись некоторых демонстрационных выступлений в «Студии Пасвей».
Их сделка придала им новой уверенности, и группа наконец-то согласилась переехать в Лондон, несмотря на то, что им приходилось радикально менять свою жизнь. В высшей степени лестный отзыв о «Last Exit» появился в Ньюкасле в «Джорнал», написанный Энди Боуном в конце 1976 года. Статья была озаглавлена «Last Exit» — по дороге на юг, к славе».