прекращение украинского гражданства в случае его утраты имеет сильный элемент произвола

Это не произвол, в правовом контексте это называется принятием решения на усмотрение (Ermessensentscheidung).

припоминаю случай на форме, когда пользователь с немецко-украинским гражданством хотел вместо выхода из гражданства Украины оформить его утрату. насколько помню, ничего у него из этого не вышло, хотя он сообщал в самые высокие инстанции, что добровольно приобрел иностранное гражданство, и прикладывал доказывающие это документы.

Согласно законодательству Украины, добровольное приобретение гражданства другого государства не обязательно будет иметь следствием утрату гражданства Украины, оно лишь является основанием для такой утраты. Аналогично Германии, где до последних изменений в StAG летом прошлого года гражданам Германии без проблем выдавали Beibehaltungsgenehmigung'и для натурализации в США. Почему же в случае натурализации в других государствах (не считая ЕС и Швейцарии) Beibehaltungsgenehmigung получить в преимущественном количестве случаев было практически невозможно? Это тоже произвол?

Поэтому ничего удивительного, что этот пользователь не утратил своего гражданства Украины, более того, никто не лишал его права оформить выход из гражданства Украины, конечный результат в результате обоих админпроцессов был бы одинаковый - прекращение его гражданства Украины.