В октябре 1995 года обозреватель ИД "Коммерсантъ" Вероника Куцылло, президент Республики Коми Юрий Спиридонов и пенсионер Роман Клебанов обратились в Конституционный суд (КС) России с жалобой о признании противоречащим Конституции закона Москвы "О сборе на компенсацию затрат городского бюджета", согласно которому россиянин, желающий получить московскую прописку, должен был заплатить пошлину в размере 500 МРОТ (около $6,1 тыс.). 4 апреля 1996 года КС РФ принял решение в пользу истцов, а 6 мая мэр Москвы Юрий Лужков отменил своим постановлением все документы о регистрации граждан, противоречащие решению КС. 19 июня 1996 года Вероника Куцылло получила прописку в Москве.
В июле 1995 года житель Твери Александр Евпак обратился в ОВД Савеловского района с просьбой зарегистрировать его в квартире, которая досталась ему в порядке наследования. Начальник ОВД отказал, сославшись на постановление правительства Москвы "О едином порядке прописки и выписки населения в городе Москве", согласно которому прописка в домах, подлежащих реконструкции или сносу, не допускается. Александр Евпак обратился в Савеловский районный суд, который 5 сентября 1995 года признал действия начальника ОВД незаконными. 14 ноября Мосгорсуд отменил решение Савеловского суда, указав на безосновательность жалобы заявителя. 14 ноября 1996 года дело направлено на рассмотрение в Верховный суд (ВС), и 25 ноября 1997 года вынесено решение в пользу истца. ВС указал на норму закона "О праве граждан РФ на свободу передвижения", в соответствии с которой собственник жилого помещения в Москве, избравший его местом своего жительства, должен зарегистрироваться в органах регистрационного учета, а этот орган обязан зарегистрировать его не позднее трех дней со дня предъявления документов.
В апреле 1998 года житель Липецкой области Андрей Иноземцев обратился в ОВД района Зюзино с просьбой зарегистрировать его в столице сроком на пять лет. Согласие собственника жилья на регистрацию у господина Иноземцева было. Однако в ОВД ему отказали, сославшись на "Правила регистрации и снятия граждан РФ с регистрационного учета по месту пребывания и по месту жительства в пределах РФ", которые еще 2 февраля 1998 года были признаны КС не соответствующими Конституции. Андрей Иноземцев, интересы которого представлял юрист ИД "Коммерсантъ" Дмитрий Жарков, пытался обжаловать действия сотрудников милиции в Зюзинском райсуде, а затем в Мосгорсуде. Однако после этих безуспешных попыток 4 июня он обратился в Верховный суд. 20 июня ВС РФ вынес решение, согласно которому положения инструкции МВД признаны незаконными и не подлежащими применению.