В принятой 28 июля 1996 года новой Конституции Украины проблема статуса крымских татар не получила какого-либо специального освещения. Ст.24 Основного Закона провозгласила, что «граждане имеют равные конституционные права и свободы и равны перед законом. Не может быть привилегий и ограничений по признакам расы, цвета кожи, политических, религиозных и иных убеждений, пола, этнического и социального происхождения, имущественного положения, места жительства, по языковым и иным признакам».[387] Правда, понятие «коренного народа» все же попало в украинскую Конституцию, однако без какой-либо конкретной привязки, согласно формулировки ст. 11 «Государство содействует консолидации и развитию украинской нации, ее исторического сознания, традиций и культуры, а также развитию этнической, культурной, религиозной самобытности всех коренных народов и национальных меньшинств Украины».[388]
Наиболее существенным моментом, вызывавшим трения между Меджлисом и украинскими властями, была проблема предоставления гражданства большому числу крымских татар, вернувшихся после 1991 года. Как уже было сказано, украинским законодательством предусматривалась довольно сложная система обретения гражданства, затруднявшая путь к нему для большого числа крымских татар. Это вызывало многочисленные нарекания со стороны международных наблюдателей, а так же привело к тому, что Меджлис объявил бойкот выборам в местные советы в 1996 году (заявив, что эта акция не носит антигосударственного характера). Впоследствии процедура получения украинского гражданства крымскими татарами была существенно упрощена, но появились новые предметы разногласий между Киевом и Меджлисом.
В частности, ВС Украины принял новый закон о выборах ВС Крыма, который упразднял квоты для татар в представительном органе полуострова. Попытки организовать противодействие этим решениям со стороны Меджлиса не увенчались успехом (в марте 1998 года Меджлис попытался организовать блокирование железнодорожных путей, но эти действия были пресечены милицией, а против их организаторов возбуждены уголовные дела). Представительный орган татар вынужден был смириться с решениями тех, чьим союзником на протяжении нескольких лет являлся.
Не продвинулась в сторону решения и проблема признания Киевом Меджлиса, который с точки зрения украинского законодательства не имеет права на существование, по крайней мере, в виде политической организации, обладающей официальным статусом. Со стороны украинских властей такой акт создавал бы нежелательный прецедент появления на территории государства институтов, не предусмотренных законами Украины, к тому же к концу 90-х годов возникли большие сомнения в том, отражает ли Меджлис интересы всей крымскотатарской общины (альтернативной Меджлису является, например НДКТ, которое отказывает ему в праве выступать от имени всех крымских татар). Напомним, что лидеры Меджлиса рассматривают эту организацию как «полномочный представительный орган», документы, регламентирующие ее деятельность, позволяют говорить о том, что она задумывалась, как структура, альтернативная официальным государственным институтам и призванная в известной степени подменить их. Ее легализация не только бы породила проблему взаимоотношений этого органа с официальными государственными, но и вызвала бы цепную реакцию создания разного рода «самоуправлений» по этническому признаку (как известно, второй подобной организацией стала т. н. «Дума русской общины», которая была создана как аналог Меджлиса, и хотя ее деятельность не получила развития, сам по себе прецедент достаточно показателен). Непризнание Меджлиса в качестве «полномочного представительного органа», однако, не означает вообще отсутствие реального статуса у этой структуры. Власти Крыма и Украины закрывают глаза на то, что Меджлис не зарегистрирован в Министерстве юстиции, и осуществляют контакты с ним как с общественной организацией. При этом в прессе неоднократно высказывалось мнение о том, что между властями и Меджлисом установился негласный паритет, выгодный как функционерам Меджлиса, так и чиновникам.[389]
Международная активность«Внешняя политика» Меджлиса включает в себя три основные линии. Первая — контакты с непризнанными государствами (не всеми подряд, а тщательно подобранными), образовавшимися как на развалинах СССР, так и за его пределами. Наиболее показательными являлись здесь контакты с Чечней. С самого начала конфликта Меджлис однозначно и недвусмысленно поддержал «борьбу чеченского народа с российским империализмом». Известно, что некоторые крымские татары участвовали в войне на стороне Чечни, а также то, что чеченские боевики находили пристанище в семьях активистов Меджлиса. Портреты Д. Дудаева являются неотъемлемым атрибутом татарских митингов, а события зимы 1997 года свидетельствуют о том, что татарские радикалы не прочь взять на вооружение и методы борьбы чеченцев.