В 1995-96 годах фракция «Созидание» развернула борьбу за смещение правительства А. Франчука, которое обвинялось в недостаточно умелом руководстве регионом. А. Франчук был отправлен в отставку с поста премьер-министра, а на его место избран А. Демиденко, занимавший до этого пост вице-премьера крымского правительства. Кабинет А. Демиденко, однако, оказался склонным в большей степени проводить политику в интересах официального Киева, нежели лидеров фракции «Созидание», чем во многом и объясняется то, что через некоторое время представители этой фракции развернули критику и этого кабинета (с деятельностью правительства А. Демиденко связаны наибольшие потери Крыма в части республиканских полномочий).
В свою очередь парламентская оппозиция обрушилась на руководство большинства ВС с обвинениями в крупных финансовых злоупотреблениях, связях с криминальными структурами и коррупции. В сентябре 1996 года оппозиция объединилась в т. н. «Антикриминальную коалицию»(32 депутата), которой удалось 9 октября 1996 года отправить в отставку спикера крымского парламента Е. Супрунюка. Отставке способствовал скандал, связанный с таинственным исчезновением спикера 24 августа 1996 года (по словам Е. Супрунюка, он был похищен и увезен неизвестными на север Крыма. Оппозиция обвинила спикера в инсценировании своего похищения в политических целях).[308] Избранный на место Е. Супрунюка «антикриминал» В. Киселев, сумел продержаться на своем посту лишь несколько месяцев, после чего был заменен одним из лидеров оправившегося от поражения «Созидания» А. Гриценко.
Отсутствие каких-либо позитивных сдвигов в экономике Крыма, окончательная утрата экономической самостоятельности в период правительства А. Демиденко, создали условия для новых изменений в крымском правительстве. К 1997 году вокруг экс-премьера А. Франчука, к этому времени депутата ВР Украины от г. Керчи, сформировался самостоятельный центр политического влияния, который начал работу по возвращению А. Франчука на крымский «политический Олимп». В начале 1997 года между крупнейшими группировками ВС Крыма было достигнуто неформальное соглашение по объединению действий, с целью возвращения А. Франчука на пост руководителя Крымского правительства. Попытка А. Демиденко заручиться поддержкой официального Киева и опереться на созданное в Крыму общественно-политическое движение («Крым — Наш дом») не увенчалась успехом. А. Демиденко был отправлен в отставку. Президент Украины Л. Кучма утвердил избрание А. Франчука Председателем Совета Министров Крыма, и вскоре последний сформировал правительство, в которое вошли как представители ПЭВК, так и люди, входившие в «Антикриминальную коалицию». С приходом А. Франчука — влиятельной фигуры в политических кругах Украины и Крыма, ожидалось наступление известной стабилизации внутрикрымской политической ситуации. Однако накануне выборов в ВР Украины в 1998 году в Крыму с новой силой вспыхнули политические баталии, которые сопровождались даже криминальными эксцессами, которые стали едва ли не нормой крымской политической жизни середины 90-х годов.
Криминал и политикаТесная связь криминальных структур и политиков — также существенная черта эпохи введения Крыма в правовое поле Украины. К середине 90-х годов на полуострове действовали несколько влиятельных мафиозных группировок (наиболее крупные: «башмаки» — называлась по имени руководителя В. Башмакова, и «Сэйлем» — от наименования ресторана в Симферополе), которые занимались рэкетом, торговлей оружием и т. д. Их расцвету способствовала длительная неразбериха с подчиненностью правоохранительных структур Крыма. Переподчинение в 1994 году крымской милиции Киеву также существенно не повлияло на ситуацию, напротив, именно с 1995 года влияние криминальных группировок на общество стало ощущаться особенно сильно. В середине 90-х в Крыму возникли целые альянсы, объединявшие криминал и теневую или полутеневую экономику. Связанные с криминальными группировками предпринимательские круги контролировали целые сектора местного хозяйства: торговлю горюче-смазочными материалами, санаторно-курортный комплекс, розничную торговлю и т. д. Криминальные группировки начали оказывать целенаправленное воздействие на местных политиков и представителей власти.
Так общеизвестными были связи между руководством ПЭВ и криминальной группировкой «Сэйлем». С помощью боевиков этой гангстерской «бригады» ПЭВКовские деятели организовывали давление на своих политических противников (так, например, в 1995 году спикер крымского парламента Е. Супрунюк организовал избиение экс-спикера С. Цекова, а затем по его заказу был убит шантажировавший его участник нападения). Через связанные с криминалом банки, близкие к ПЭВ предпринимательские структуры осуществляли крупные хищения и т. д. В свою очередь политики пэвковской ориентации обвиняли своих оппонентов из «антикриминальной коалиции» в том, что они опираются на другую криминальную группировку — «Башмаков». Время 1995-98 годов получило название эпохи «криминального беспредела».[309] Это было время почти открытой коррупции и уголовного террора. На политиков и бизнесменов организовывались покушения, кровавые конфликты возникали и между представителями преступных групп. На выборах в местные органы власти в 1995 году в районные и городские советы Крыма прошли 44 человека, в разной степени связанные с криминальными структурами. Криминализация политической жизни глубоко дискредитировала органы республиканской власти, лишая их какой-либо поддержки со стороны населения.