У Стинга не было проблем с уходом Генри, но Стюарт сохранял некоторую симпатию к нему, потому что считал его хорошим другом и родственной душой.
Фактически не желая открыто противостоять Генри, группа даже провела ряд выступлений вчетвером. «Их первый выход в «Камден Мьюзик Машин» в Лондоне был ужасным. Неудивительно, что Генри и Энди не могли подходить друг другу. Генри позже объяснял: «Энди был гитаристом-виртуозом. «Делай это! Ты не можешь? О…» Я чувствовал себя молодым лисенком, которого заставляют слушать старого волка». И это было мягко сказано!
Трение между двумя гитаристами достигло пика на фестивале панк-музыки в Монт-де-Марсане, неподалеку от Бордо во Франции в начале августа 1977 года. Последовали споры по поводу усилителей, и Генри был к концу выступления настолько раздражен, что отказался разговаривать с остальными членами группы и ушел в припадке гнева со своей подружкой. Неделю (или около того) спустя сеанс записи под наблюдением продюсера, композитора-песенника и исполнителя Джона Кейла, обернулся перебранкой, потому что ни Энди, ни Стинг не любили, когда им дают указания. Генри Падовани ощущал, что близится конец.
Вечером 12 августа ему позвонил Стюарт и сказал, что все кончено и Генри направился на Корсику — туда, где был его дом, на вполне заслуженный отдых. Спустя несколько месяцев он вернулся в музыкальный бизнес, но никогда полностью не оправился от уроков, полученных в «Полиции».
Тем временем брат Стюарта, прозорливый бизнесмен Майлз, все еще держался от группы на расстоянии. Случилось так, что на него также произвел сильное отрицательное впечатление Энди Саммерс. «У этого парня короткие волосы и брюки клеш», — сказал он своему брату Стюарту сердито, совершенно игнорируя музыкальный талант Энди.
Неудивительно, что и Энди почувствовал неодобрение Майлза. «Это моментально заставило меня не желать иметь с ним дело. Я полагал, что на Стюарта оказывал чрезмерное влияние его старший брат».
Однако Стинг был очень доволен тем, что Энди был принят. Он показал себя совершенно другим человеком, когда присоединился к «Полиции». Энди был безупречным исполнителем-профессионалом, и он настаивал на том, чтобы группа репетировала каждую песню каждый вечер для следующей недели.
Новое трио дебютировало в Бирмингемском клубе «Ребекка» 18 августа 1977 года. Стинг впервые осознал, что у них все идет как надо. Они, пожалуй, действительно слились воедино как группа, хотя было еще много препятствий, которые предстояло преодолеть.
Самой большой проблемой стал имидж. Панк-клубы и их фанаты уже знали, что «Полиция» не имеет никакого отношения к их стилю музыки. Заказы на выступления иссякли, а британские поклонники рока и потенциальные спонсоры были в равной степени сбиты с толку, куда же причислить эту группу. Тогда группа решила нанять на полную ставку менеджера и взяла Лоренса Импли, школьного товарища Стюарта из Милфилда. Майлз Копленд остался «на заднем сиденье».
Один раз они думали, что их зарезервировали как поддерживающую группу для выступления в Голландии. Они сложили свои гитары и один усилитель в «ситроен» Энди Саммерса, но, как оказалось, лишь только для того, чтобы добраться до Роттердама и обнаружить, что их выступления не были запланированы.
Затем они умудрились пристроиться в качестве поддерживающей группы в Париже и направились во французскую столицу. 20 сентября 1977 года они играли в Париже. Однако дела шли все хуже и хуже, и музыканты не могли позволить себе платить за жилье. Всё закончилось тем, что спали в машине после выступлений в районе красных фонарей.
Вот тогда-то Стинг и заметил (впервые) большое количество проституток на улицах, которые вдохновили его на одну из самых прекрасных композиций. «Это было впервые: я видел проституцию на улицах, и эти птички были действительно прекрасны. В голове у меня вертелась мелодия, и я представил себя влюбленным в одну из таких девушек. Я имею в виду, что у них обязательно есть парни. Как бы я себя чувствовал?»
Роксана!