В феврале 2006 года в Россвязьнадзор поступило заявление дочернего предприятия «ВымпелКома», ЗАО «Восток-Запад Телеком», о предоставлении лицензии на услуги сотовой связи в Дальневосточном регионе. К заявлению были приложены решения ГКРЧ, выданные иному юридическому лицу — ООО «Восток-Запад Телеком». В связи с этим Россвязьнадзор решил отказать в выдаче лицензии. «ВымпелКом» обжаловал отказ в Арбитражном суде Москвы, который 18 августа 2006 года принял сторону истца. Однако это решение было оспорено Россвязьнадзором: 7 ноября Девятый арбитражный апелляционный суд отменил его, подтвердив законность отказа Россвязьнадзора в выдаче лицензии ЗАО «Восток-Запад Телеком». А 10 ноября тот же суд признал законным отказ ГКРЧ выделить частоты для сети «Билайн» на Дальнем Востоке.