Я просмотрел ФЗ-62 "Закон о Гражданстве РФ", порядка выхода из гражданства не нашел.
По ссылке на консульство РФ (пару сообщений выше) есть формуляр - почему он не подходит?
Стоит ли мне звонить в Консульство?

Не надо никуда звонить - откройте
Консульский департамент МИД России>Консульские функции за рубежом
Выбирайте раздел Вопросы гражданства
Там всё законодательство по этой теме.