В том же феврале группа выступила на организованном фондом «Ночлежка» и Гаккелем фестивале «Другая музыка» (11-го) и на концерте памяти Александра Башлачева (17-го), в апреле разогревала зал на питерском концерте Питера Хэммилла (VAN DER GRAAF GENERATOR), а в июне делала то же на выступлении Майкла Наймана.
Месяц спустя в составе группы произошли очередные замены: место Гаккеля занял виолончелист Василий Попов из оркестра Филармонии, а барабанщиком стал Александр Погорелов (БАРАБАСЫ, BARRACUDAS). Шавкунов окончательно закрепился в АКВАРИУМЕ, однако при возможности выступал с ВЕРМИШЕЛЬЮ и позже: в частности, в сентябре 1998-го гастролировал с ней в Москве.
В октябре во Дворце Молодежи состоялся первый в Питере фестиваль Сергея Курехина S.K.I.F., для участия в котором в VERMICELLI ORCHESTRA вернулся Гаккель, игравший с Поповым в две виолончели. Визиты в столицу наконец возымели результат, когда в декабре группа заключила контракт с «Boheme Music» Андрея Феофанова (фри-джазового музыканта, ставшего издателем).
Имея ясную перспективу, VERMICELLI ORCHESTRA в январе-апреле записали на «ПСГ» с Докшиным за пультом свой второй альбом «Византия». Основные партии флейты исполнил Николай Мохов (Сечкарева играла лишь в трех номерах), за барабаны вернулся Семенов, а в качестве гостей присутствовали Гаккель, Шар и Алексей Селютин (фагот).
В мае группа выступила на фестивале кельтской музыки в Москве, после чего «Boheme» делегировала ее на конференцию «Forte Riga» в Латвию. Оказалось, что у Кадырова и Семенова нет загранпаспортов, а Мохов занят, поэтому в Ригу с ВЕРМИШЕЛЬЮ отправились Гаккель, Трощенков, Илья Розовский, гитара, и Юлия Антипенко, флейта.
После фестиваля в группе произошло очередное размежевание, и ее покинул Кадыров, место которого окончательно занял Розовский. Летом 1999 года ОРКЕСТР отметился на фестивале «Кук-Арт» в Пушкине, играл на презентации альбома с музыкой Сергея Курехина к фильму «Господин оформитель», еще раз посетил Москву и дал несколько клубных концертов. По завершении сезона Гаккель, который решил закончить музыкальную карьеру, ушел (хотя позднее появлялся на концертах ВЕРМИШЕЛИ как приглашенный музыкант), Попов был постоянно занят, и единственным виолончелистом остался Владимир Юнович, который уже подменял Гаккеля весной, когда тот лечил вывих плеча.
В ноябре 1999 года новым барабанщиком VERMICELLI ORCHESTRA стал Павел Иванов (его старший брат Константин в 80-х барабанил в ДИЛИЖАНСЕ, СОЮЗЕ и т. д.). Семенов ушел в BLACK MAGIC.
С началом Нового 2000 года группа продолжила интенсивно концертировать в Питере и Москве: 18 марта в клубе «Молоко» состоялся один из лучших – по мнению музыкантов – концертов ВЕРМИШЕЛИ за всю ее историю. В апреле она сыграла на фестивале S.K.I.F.-4. 19 апреля свет увидел альбом «Византия», чему была посвящена виртуальная пресс-конференция на «Радио РОКС» 22 мая. В июне были фестиваль «Анимализм» в клубе «Зоопарк» (на флейте вновь играла Сечкарева), III фестиваль кельтской музыки «Moscow Fleadh» и фестиваль «Рок-держава 2000» в ДК им. Горбунова (Москва).
На дне рождения Дюши Романова (июль) с ВЕРМИШЕЛЬЮ на сцену вышли Мохов, Сечкарева и Гаккель, однако тем же летом в группе появился постоянный флейтист Тимур Богатырев. В сентябре в Петропавловской крепости состоялся фестиваль «Арт-Ковчег», где на барабанах с группой играл Александр Емельянов (BASTONADA, ГЕЗЫ), а в Хельсинки – фестиваль «Благовест». Помимо того, на группу наконец обратило внимание телевидение, и начиная с осени ее периодически снимали для разных передач. Существенную роль в организации внутренней и внешней жизни группы сыграл появившийся в ее рядах директор Артем Тамазов.
В январе 2001 года «Manchester Files» переиздал «Анабасис» в России. Месяцем позже группа выступила в программе «Антропология», после чего совершила первое в своей истории турне по городам Сибири.
Ввиду того, что большинство музыкантов VERMICELLI ORCHESTRA постоянно занято в тех или иных академических составах, группу преследовала вечная текучесть кадров: иногда Щуракову приходилось репетировать одновременно с несколькими музыкантами, дабы быть готовым к любому предложению сыграть концерт, хотя и это срабатывало не всегда.
Так, в марте 2001-го на концертах в Москве ВЕРМИШЕЛЬ была без виолончели – ее заменяла гитара, на которой играл Игорь Бобрицкий (СЛОН В ТЕМНОТЕ). В том же месяце в клубе «JFC» с группой дебютировала виолончелистка Юлия Рычагова, а в мае компанию ей составил Илья Карташов. Весной они опять участвовали в фестивале S.K.I.F.; летом побывали на фестивале этнической музыки «Faces» в Финляндии и сыграли на концерте памяти Дюши Романова в клубе «Спартак».
Поскольку тогда же Павел Иванов на несколько месяцев отбыл в Германию, в «Спартаке» за него играл Трощенков, а осенью и зимой Павлова заменяли Дмитрий Товстопят из BASTONADA и ШКАЛЫ РИХТЕРА, а также перкуссионист Дмитрий Веселов (STEAM, АКВАРИУМ).