Тогда же Паращук и Левин объединились с единомышленниками из DDT и АЛИСЫ в ностальгическом кавер-бэнде ДУБЫ-КОЛДУНЫ, который в течение 1993–1996 годов сыграл десятки концертов в Питере и Москве, а также записал два удачных альбома, в которых питерские рок-н-ролльщики перепели массу популярных песен времен своей трудной комсомольской юности.
В середине 90-х НЭП почти не выступал дома, зато регулярно гастролировал в Европе, объездив практически всю Германию. В апреле 1996 года Першин решил покинуть музыку – его место вновь занял давно расставшийся с ТЕЛЕВИЗОРОМ и игравший в группе DOWN TOWN WILD Владимира Козлова (экс-СЛМР) Игорь Федоров. Его сценический дебют в составе НЭП состоялся 28 сентября 1996 года на открытии сезона в клубе «Перевал», когда они представили слушателям материал своего нового альбома «Вот она, любовь», записанного следующей зимой на студии DDT. Его звукорежиссером стал Женя Левин, который к тому моменту начал успешно совмещать выступления на сцене с работой в студии (с самими DDT, РАЗНЫМИ ЛЮДЬМИ и т. д.).
В начале 1998 года НЭП временно потерял трудоспособность: Левин гастролировал с АЛИСОЙ, Федоров – с ЧИЖОМ&Co, Жданов выступал с собственным джазовым трио, а Паращук лечил сломанную ногу – по части изувеченных конечностей НЭП вообще можно считать чемпионом (впрочем, к музыке эти истории отношения не имеют).
Активная сессионная деятельность в конечном счете привела к радикальным изменениям в составе: в начале 1999 года место окончательно ушедшего в АЛИСУ Левина занял известный питерский гитарист Игорь Романов (ранее РОССИЯНЕ, ЗЕМЛЯНЕ, СОЮЗ; помимо того, на протяжении 90-х он регулярно выступал и записал три альбома с собственным инструментальным пауэр-трио ROMANOFF), а с той же осени, когда НЭП вернулся к активному концертированию, Игоря Федорова сменил за барабанами Андрей Вдовиченко (экс-КОРЧАГИН И СЫНОВЬЯ, ЛУНОФОБИЯ).
14 декабря 1999 года в ДК им. Ленсовета при большом стечении народа НЭП отметил свое «условное» (поскольку через месяц им реально исполнилось двенадцать) десятилетие при участии множества гостей, в числе которых были музыканты групп DDT, АЛИСА, ТЕЛЕВИЗОР, СЕРЬГА, КС, ЧИЖ&Co и т. д.
Весной 2000 года все альбомы группы были переизданы на кассетах под лэйблом магазина «Караван». Тогда же в ее репертуаре появилась песня «Я болею за „Зенит“», которая стала настоящим гимном болельщиков футбольной команды из Питера: НЭП играл ее не только на своих концертах и фестивалях, но и на собраниях «Невского фронта» – официального объединения болельщиков «Зенита». 7 мая, в день инаугурации президента Путина, НЭП выступил на рок-фестивале «Выбор России» на питерском стадионе «Автомобилист» перед более чем двадцатитысячной аудиторией, с энтузиазмом подхватившей их лихой припев: «Вперед, за Питер!»
В феврале 2001 года НЭП был гостем фестиваля «Прорыв», став связующим звеном между открывавшей фестиваль АЛИСОЙ и обоймой из двух с лишним десятков молодых питерских групп. 31 марта они принимали участие в грандиозном фестивале на стадионе СКА в Минске – в компании с КРЕМАТОРИЕМ, БРАТЬЯМИ КАРАМАЗОВЫМИ и… URIAH HEEP! На барабанах с ними там – по прошествии длительного времени – снова играл Першин (КАТЮША, Вадим Курылев и т. д.), который подменял находившегося на гастролях в США с театром Вдовиченко.
1 июля 2001 года НЭП, по уже сложившейся традиции, открыл программу питерского рок-фестиваля «Окна открой!» на стадионе им. Кирова – на фоне того, что накануне «Зенит» наголову разбил московский «Спартак», футбольный гимн «Я болею за „Зенит“» прозвучал особенно жизнеутверждающе.
С оживлением концертной практики обновления, начатые «Караван Рекордз» в 2000 году, коснулись и дискографии группы: так, в июле «Grand Records» в серии «Энциклопедия русского рока» выпустила сборник из восемнадцати ее лучших песен, записанных с 1989-го по 2000-й. Помимо того, unplugged концерт НЭП 13 апреля 2001 года в 344-й питерской гимназии был записан для запланированного к изданию концертного альбома.
В конце 2001 года Саша Фомин, с середины 90-х постоянно живущий в Нью-Йорке, неожиданно решил вернуться в музыку, став барабанщиком молодой, но уже обратившей на себя внимание группы INTERZONA.
В декабре 2003-го НЭП поджидал очередной сюрприз: когда АЛИСУ покинули двое из ее основателей, Андрей Шаталин и Михаил Нефедов, на их места Кинчев пригласил новых «легионеров» из НЭП, Игоря Романова и Андрея Вдовиченко, что существенно ограничило мобильность группы, поэтому в дальнейшем НЭП выступал лишь от случая к случаю: либо на крупных фестивалях, либо на акциях «Невского фронта».