После Ветлицкой я сделал для себя вывод: я уже не пойду с серенькой. Но мне не нужно рядом с собой еще одно Имя. Мне просто нужен хороший человек. Сказать же, что на Наташе я «обжегся», это значит признать, что она — роковая женщина. На самом деле роковой — я. Потому что я моложе. И я уехал и сказал ей: «До свидания». Тогда многое совпало: мой отъезд в круиз на 24 дня и наше расставание. Мы тихо отошли друг от друга, без слез и скандалов. Мы остались друзьями. Практически всегда с девушками, с которыми у меня был роман, я расстаюсь тихо-мирно. И встретиться нам по старой дружбе ничто не мешает…»

Характерный случай, связанный с особым отношением женщин к Сташевскому, произошел в 1995 году. Однажды после концерта к нему за кулисы пришли две женщины (кстати, замужние) и предложили ему 5 тысяч долларов за то, чтобы он провел с ними «ночь любви». Сташевский поначалу подумал, что женщины шутят, но когда те при нем стали отсчитывать деньги и уже готовы были отдать их ему, понял, что это не розыгрыш. Посетительницы действительно были настроены решительно и намеревались тут же, не дав ему даже как следует привести себя в порядок, увезти с собою. Влада лишь на несколько секунд охватило смятение, после чего он взял себя в руки и коротко объяснил женщинам, что их желание из области неосуществимого. Но женщин его спокойный голос совершенно не вразумил. «Как это неосуществимо? — искренне удивилась одна из них. — Да за деньги все можно купить. Не хочешь пять тысяч, на тебе десять!» И женщина вновь полезла в свою сумочку. Дело принимало серьезный оборот, и Сташевский понял, что одному ему с посетительницами никак не справиться. Поэтому он не нашел ничего лучшего, как пригласить в гримерку охрану, и та чуть ли не под руки выставила неугомонных девиц за дверь. Напоследок одна из женщин бросила взгляд на певца, и тот прочел в нем такое неподдельное удивление (мол, ты, чувак, даешь: отказываешься сразу от двух удовольствий — от секса и кучи баксов!), что ему стало немного не по себе.

А вот другой случай, произошедший зимой того же года, который характеризует Сташевского как человека смелого и умеющего постоять не только за себя, но и за даму. Послушаем его собственный рассказ:

«Произошло это на Таганке. Мы были с другом, его женой и сестрой. Отошли купить сигареты, а какие-то «орлы» уже заталкивали наших девушек в машину, какую-то «убитую» «шестерку». Их было человек пять. Была крепкая драка, мы хорошо их отделали. У меня была подбита губа, синяк под глазом. Я не люблю, когда меня доводят до крайности, белки наливаются кровью, и пру так… Но нас было мало, а лучшая защита — нападение. В конце концов я просто достал большой пистолет фирмы «Майами-Рек», автоматический, 12-зарядный, девятый калибр. Они не верили, что я буду стрелять. Оставалось снять с предохранителя. Я крикнул: «На землю все! А теперь дружно встали, сели в машину и уехали». В такой ситуации главное — не дергаться, вести себя как ни в чем не бывало…»

Не менее насыщенно, чем личная жизнь, складывалась и творческая деятельность Сташевского. Ежегодно в свет выходил один альбом певца (1994 г. — «Любовь здесь больше не живет», 1995 г. — «Не верь мне, милая»). В 1996 году в результате читательского референдума газеты «Московский комсомолец» Сташевский был назван лучшим певцом года. В том же году он получил премию «Овация» в номинации «Шлягер-96» за песню «Позови меня в ночи».