А погуглить наверно уже не судьба или неимоверно трудно?

Но ему по телефону сказали, чтобы он посмотрел ещё раз какие документы тебует украинское консульство

правильно посоветовали. Простой набор "Ukraine botschaft" выдаёт моментально ссылку на консульство Украины в Германии, а там уже переходим в раздел консульских услуг

http://germany.mfa.gov.ua/ua/consular-affairs/...

Для оформлення виходу із громадянства України необхідно особисто подати до консульської установи за кордоном кожною повнолітньою особою (від 18 років) наступні документи:
1. Заяву в чотирьох примірниках про вихід з громадянства України.
2. Свідоцтво про народження та 1 копію;
3. 4 фотокартки (розміром 35 х 45 мм);
4. Паспорт громадянина України для виїзду за кордон з відмітками про виїзд на постійне проживання за кордон та перебування на консульському обліку в Посольстві України або іншій консульській установі України у ФРН та 4 копії всіх сторінок паспорта;
5. Один із таких документів:
- документ, який свідчить, що заявник отримав громадянство ФРН (Einbürgerungsurkunde) та 4 копії;
- документ, виданий уповноваженим органом ФРН про те, що громадянин України отримає громадянство ФРН, якщо вийде з громадянства України (Einbürgerungszusicherung) та 4 копії.Для виходу з громадянства України разом з дитиною, яка виїхала разом із батьками на постійне проживання за кордон (або вже народилась за кордоном), один із батьків дитини у заяві про свій вихід з громадянства України одночасно порушує клопотання про вихід дитини з громадянства України разом з ним.До заяви додаються:
6. Свідоцтво про народження дитини та 4 копії;
7. Копія документа, який підтверджує перебування дитини у громадянстві України та 4 копії (для дітей, народжених після 01.03.2001 р. – довідка про реєстрацію дитини громадянином України. У випадку, якщо дитина народилась до 01.03.2001 р. за кордоном, на підтвердження належності до громадянства України дитини подається копія паспорта обох батьків);
8. Один із таких документів:
- документ, який свідчить, що дитина отримала громадянство ФРН (Einbürgerungsurkunde) та 4 копії;
- документ, виданий уповноваженим органом ФРН про те, що дитина отримає громадянство ФРН, якщо вийде з громадянства України, (Einbürgerungszusicherung) та 4 копії;- документ, який свідчить, що дитина набула громадянства ФРН (Staatsangehörigkeitsausweis) та 4 копії;У разі відсутності зазначених документів у дитини, особа подає німецький дитячий проїзний документ (Kinderreisepass), нотаріально засвідчену та завірену штампом APOSTILLE копію його першої сторінки де вказано, що дитина є громадянином ФРН (та 3 копії), а також оригінал її перекладу на українську мову завірену штампом APOSTILLE та його 3 копії.
9. Заяву дитини віком від 14 до 18 років про згоду на вихід з громадянства України в 4 примірниках (нотаріально засвідчену);Увага! У випадку наявності у дитини самостійного паспортного документа громадянина України, до матеріалів справи про вихід із громадянства подається його оригінал та 4 копії всіх сторінок. У випадку відмінності прізвищ батьків з прізвищами дітей, або відмінності прізвищ особи у гарантії та паспорті громадянина - до матеріалів справи подаються документи про переміну ними прізвищ, засвідчені штампом Апостилю або легалізовані у встановленому порядку та їх переклади на українську мову, зокрема оригінал і 4 копії свідоцтва про шлюб/розірвання шлюбу (якщо шлюб реєструвався в Україні). У разі відсутності свідоцтва про укладення шлюбу, подається довідка РАЦС про його реєстрацію. У разі реєстрації шлюбу на території ФРН подається один із наступних документів:
- свідоцтво про укладення шлюбу - Eheurkunde, в якому зазначені прізвища після шлюбу, його 4 копії, оригінал та 3 копії його перекладу;
- cвідоцтво про шлюб міжнародного зразка (Auszug aus dem Heiratsregister, - Heiratseintrag), його 4 копії, оригінал та 3 копії його перекладу;
- довідка про укладення шлюбу (Bescheinigung über die Eheschließung) із зазначенням прізвищ після його укладення, її 4 копії та 4 копії її перекладу, а також, рішення суду про його/їх розірвання (якщо реєструвалось).
10. Завірену банківською установою квитанцію про сплату консульського збору в розмірі 270 €.Гроші просимо переказувати на рахунок Посольства. Банківські реквізити Посольства: Botschaft der Ukraine, Konto 266 74 75, BLZ 100 400 00 Commerzbank AG Berlin, IBAN DE64 1004 0000 0266 7475 00, BIC COBADEFFXXX
11. Три конверти з маркою 3,60 євро з Вашою зворотною адресою в якості отримувача, зазначеною німецькою мовою.

Точно могу вам сказать, что подавал на выход в марте этого года и никакого перевода и апостиля на Meldebescheinigung я не делал. Более того, где-то, для ПМЖ вроде, как раз и стояло, что на Meldebescheinigung никакого перевода не надо. Но мнe искать лень, т.к. оно мне не надo

P.S. А муж стоит на постоянном консулъском учете?