Это называется Hinnahme der Mehrstaatigkeit и регулируется §12 StAG. Там, в частности, сказано:
[можно, если] der ausländische Staat die Entlassung aus der Staatsangehörigkeit aus Gründen versagt hat, die der Ausländer nicht zu vertreten hat, oder von unzumutbaren Bedingungen abhängig macht oder über den vollständigen und formgerechten Entlassungsantrag nicht in angemessener Zeit entschieden hat
Возникает вопрос, что такое angemessene Zeit. Ответ находим документе, который называется vorläufige Anwendungshinweise zum StAG от 17.04.2009 . Там написано:
12.1.2.3.3 Dritte Fallgruppe (Nichtbescheidung eines Entlassungsantrags)
Mehrstaatigkeit ist regelmäßig hinzunehmen, wenn zwei Jahre nach Einreichen eines voll-ständigen und formgerechten Entlassungsan-trags eine Entlassung aus der Staatsangehörig-keit nicht erfolgt und mit einer Entscheidung innerhalb der nächsten sechs Monate nicht zu rechnen ist.

Одного факта, что в Украине сейчас реструктуризация органов, занимающихся вопросами гражданства, недостаточно. На данный момент для получения немецкого гражданства "unter Hinnahme von Mehrstaatigkeit" из-за слишком долгого рассмотрения дела о выходе из украинского гражданства нужно, грубо говоря, не быть "выпущеным" 2 года и (так мне неоднократно говорили в EBH) получить от украинских органов справку, в которой говорится, что дело в ближайшие 6 месяцев не будет рассмотрено. У меня очень большие сомнения, что такие справки вообще выдаются
С другой стороны, сейчас EBH по всей Германии видят, что дела с украинскими гражданами тормозятся. Возможно, это может привести к корректировке der vorläufigen Anwendungshinweise в нашу пользу...