Правильно ли я понимаю, что если это их право, то, в принципе, даже если я найду правильный орган Литвы, который согласится направить им нужный документ с текстом, который они хотят видеть, то они могут им не пользоваться и попросту проигнорировать и никакой Утраты не инициировать?

Суть верна. Это их дискреционные полномочия.

Подскажите еще пожалуйста где это все прописано, в каком законе? А то не могу найти никак

КУ

Стаття 19. Правовий порядок в Україні ґрунтується на засадах, відповідно до яких ніхто не може бути примушений робити те, що не передбачено законодавством.
Органи державної влади та органи місцевого самоврядування, їх посадові особи зобов'язані діяти лише на підставі, в межах повноважень та у спосіб, що передбачені Конституцією та законами України.

Научно-практический комментарий к КУ

Одним із пріоритетних має бути принцип, за яким ніхто не може бути примушений робити те, що не передбачено законодавством. Тобто держава мусить бути гарантом не лише належної реалізації пере-дбачених Конституцією і законами прав і свобод людини і громадянина, а й неприпустимості не пере-дбачених Конституцією і законами втручання в життя і діяльність особи та примусового впливу на неї, тобто гарантом від свавілля, беззаконня, самоуправства, зловживання та вольових рішень органів державної влади і місцевого самоврядування, їх посадових осіб.

В законе нет прямой нормы, что МЗС, МСУ ОБЯЗАНЫ выполнить действия для утраты вами гражданства. Потому то нельзя требовать от них выполнение этого. Есть основания для утраты гражданства (ст. 19 закона), есть полномочия у органов (ст. 22-25), есть порядок обжалования действий (ст. 26-28), но нет нигде в законе прямой обязанности для этих органов проводить утрату гражданства.

Питання організації виконання Закону України "Про громадян...

III. Документи, що подаються для припинення громадянства України внаслідок його втрати, а також для скасування рішень про оформлення набуття громадянства України
87. Для припинення громадянства України внаслідок його втрати органи міграційної служби, дипломатичні представництва чи консульські установи України готують та подають:
а) подання про втрату громадянства України;
б) документ, що підтверджує перебування особи у громадянстві України;
в) один із таких документів:
- документ, що підтверджує добровільне набуття громадянином України громадянства іншої держави, разом із документом, який підтверджує, що на момент такого набуття громадянин України досяг повноліття (у випадку, передбаченому пунктом 1 частини першої статті 19 Закону);
- документ, який підтверджує, що особа набула громадянство України на підставі статті 9 Закону внаслідок обману, свідомого подання неправдивих відомостей або фальшивих документів (довідка органу міграційної служби, дипломатичного представництва чи консульської установи про те, що іноземець, який подав зобов'язання припинити іноземне громадянство відповідно до абзацу першого пункту 2 частини другої статті 9 Закону, не подав документ про припинення цього громадянства, виданий уповноваженим органом відповідної держави, до уповноваженого органу України протягом двох років з моменту прийняття його до громадянства України, а незалежні від особи причини неотримання документа про припинення іноземного громадянства не існують; інформація органу міграційної служби про те, що іноземець, який подав декларацію про відмову від іноземного громадянства, не повернув паспорт іноземної держави до уповноважених органів цієї держави; інформація про те, що на момент прийняття до громадянства України існували підстави, за наявності яких особа не приймається до громадянства України; інформація про інші неправдиві відомості та фальшиві документи, які були подані на підтвердження виконання умов прийняття до громадянства України);
- документ, який підтверджує, що громадянин України добровільно вступив на військову службу іншої держави, яка відповідно до законодавства цієї держави не є загальним військовим обов'язком чи альтернативною (невійськовою) службою;
г) документ, який підтверджує, що громадянин України внаслідок втрати громадянства України не стане особою без громадянства. Такий документ не вимагається в тому випадку, коли оформлення документів про припинення громадянства України внаслідок втрати здійснюється відповідно до положень пункту 2 частини першої статті 19 Закону.
88. Для скасування рішень про оформлення набуття громадянства України відповідно до статті 21 Закону органами міграційної служби, дипломатичними представництвами чи консульськими установами України готуються такі документи:
а) подання про скасування рішення про оформлення набуття громадянства України;
б) документи, які підтверджують, що особа набула громадянство України за територіальним походженням (стаття 8 Закону) або була поновлена у громадянстві України (стаття 10 Закону) шляхом обману, внаслідок подання свідомо неправдивих відомостей або фальшивих документів, приховування будь-якого суттєвого факту, за наявності якого особа не може набути громадянства України (довідка органу міграційної служби, дипломатичного представництва чи консульської установи про те, що іноземець, який подав зобов'язання припинити іноземне громадянство, не подав документ про припинення цього громадянства, виданий уповноваженим органом відповідної держави, до уповноваженого органу України протягом двох років з моменту реєстрації його громадянином України, а незалежні від особи причини неотримання документа про припинення іноземного громадянства не існують (частина п'ята статті 8 та частина друга статті 10 Закону); інформація органу міграційної служби про те, що іноземець, який подав декларацію про відмову від іноземного громадянства, не повернув паспорт іноземної держави до уповноважених органів цієї держави (частина восьма статті 8 та частина сьома статті 10); інформація про те, що на момент реєстрації громадянином України існували підстави, за наявності яких особа не поновлюється у громадянстві України (частини перша та друга статті 10 з урахуванням частини п'ятої статті 9 Закону; частина п'ята статті 10 Закону); інформація про інші неправдиві відомості та фальшиві документи, які були подані для набуття громадянства України відповідно до статей 8 та 10 Закону, або інформація про приховування будь-якого суттєвого факту, за наявності якого особа не може набути громадянство України відповідно до статей 8 та 10 Закону.

Как видите мало подтвердить наличие гражданства иного государства, а надо еще подтвердить, что оно получено добровольно.

104. Про виявлення підстави для втрати громадянства України особою, яка проживає на території України, управління, відділ (сектор) міграційної служби в районі, районі у місті, місті обласного, республіканського (Автономної Республіки Крим) значення за місцем проживання особи повідомляє головне управління (управління) міграційної служби в Автономній Республіці Крим, області, містах Києві та Севастополі.
Головне управління (управління) міграційної служби в Автономній Республіці Крим, області, містах Києві та Севастополі перевіряє наявність підстави для втрати громадянства України.
У разі необхідності головне управління (управління) міграційної служби в Автономній Республіці Крим, області, містах Києві та Севастополі може звернутися до органів Служби безпеки України для перевірки у межах їх компетенції наявності підстави для втрати громадянства України. Про результати перевірки органи Служби безпеки України повідомляють головне управління (управління) міграційної служби в Автономній Республіці Крим, області, містах Києві та Севастополі не пізніш як у двомісячний строк з дня одержання звернення.
У разі підтвердження наявності підстави для втрати громадянства України головне управління (управління) міграційної служби в Автономній Республіці Крим, області, містах Києві та Севастополі готує подання про втрату особою громадянства України та надсилає його разом із документами, передбаченими підпунктами "б" і "в" статті 87 цього Порядку, до Державної міграційної служби України.
Державна міграційна служба України розглядає подання про втрату громадянства України та подані разом із ним документи.
У разі підтвердження наявності підстави для втрати громадянства України Державна міграційна служба України затверджує подання про втрату громадянства України та надсилає його разом із поданими документами до Комісії при Президентові України з питань громадянства.

......
108. У разі виявлення підстави для втрати громадянства України особою, яка постійно проживає за кордоном, дипломатичне представництво чи консульська установа України готує подання про втрату особою громадянства України та надсилає його разом з документами, передбаченими підпунктами "б" і "в" статті 87 цього Порядку, до Міністерства закордонних справ України.
Міністерство закордонних справ України розглядає подання про втрату громадянства України та подані разом з ним документи, надсилає зазначені подання та подані разом з ним документи до Міністерства внутрішніх справ України і Служби безпеки України для перевірки у межах їх компетенції наявності підстави для втрати громадянства України. Міністерство внутрішніх справ України та Служба безпеки України повідомляють про результати перевірки Міністерство закордонних справ України не пізніш як у двомісячний строк з дня одержання документів.
У разі підтвердження наявності підстави для втрати громадянства України Міністерство закордонних справ України затверджує подання про втрату громадянства України та надсилає його разом з поданими документами до Комісії при Президентові України з питань громадянства.

Положения Порядка отдают сугубо на откуп ведомств вопрос выявления, проверки и оценки оснований, принятия решения о подготовке представления Президенту. Без участия лица, которое утратит гражданство. А под компетентным органом, который упомянут в ответе вам от МСУ и дает подтверждение, следует, видимо, понимать СБУ.