Das Einwohnermeldeamt kann euch nicht einfach so abwimmeln und euch zum Standesamt verweisen. Während eine Nachbeurkundung der Eheschließung einen Antrag von euch erfordert und für die Anerkennung der Ehe im deutschen Recht kein Anerkennungsverfahren vorgesehen ist, kann man von euch auch nicht verlangen, dass ihr die Ehe ins Eheregister nachregistriert.
Das Melderegister ist kein Personenstandsregister. Außerdem muss die örtliche Ordnungsbehörde von Amts wegen die Korrektheit des Melderegistereintrags ermitteln, sofern es Hinweise auf unrichtige oder unvollständige Daten hat, § 6 Abs. 3 BMG
https://www.gesetze-im-internet.de/bmg/__6.html . D.h. wenn du denen eine Heiratsurkunde mit Legalisation oder Apostille + Übersetzung vorlegst, dann kann das Einwohnermeldeamt nicht erklären, dass du zum Standesamt gehen sollst und das mit denen klärst. Der Sachbearbeiter muss den Hinweis eigenständig untersuchen darf von dir nur Nachweise verlangen. Wenn er dann intern das Standesamt konsultiert, dann ist es seine Sache aber kann dir egal sein. Du willst ja nur einen Eintrag im Melderegister zu verheiratet ändern, damit ihr steuerrechtlich zusammen veranlagen könnt.
Das Ausländeramt, dass dem Visum zugestimmt hat, muss ja de Ehe anerkannt haben, damit diese das FZF-Visum erteilt.
Und jetzt komm der Hammer: Das Ausländeramt, das Einwohnermeldeamt und das Standesamt sind ein und dieselbe Behörde. Wenn also das Ausländeramt die Eheschließung im Visumverfahren anerkannt hat, kann jetzt das Einwohnermeldeamt nicht sagen dass diese die Ehe nicht anerkennt.
Du hast natürlich mehrere Optionen.
a. Du gehst zum Standesamt und schaust was die wollen. Vielleicht lebst du in einem Landkreis wo der Standesbeamte auch den Familienstand im Melderegister ändert. Aber wohnst du auch in Berlin, dann würde das mich echt wundern.
b. Wir sind hier im Bereich Bundesmeldegesetz und DSGVO. Ihr habt das Recht auf korrekte Eintragung im Melderegister. Also nochmal hin und nochmal auf alles hinweisen und schriftlichen Antrag stellen, dass man den Eintrag im Melderegister korrigiert. Ggf. zum Vorgesetzten etc. eskalieren.
c. Zuzüglich zu b kannst du natürlich beim Datenschutzbeauftragten der Behörde und Landesdatenschutzbeauftragten dich beschweren. In Berlin kann es aber wahrscheinlich lange dauern.
d. § 123 VwGO, wenn dein Einkommen relativ gering ist und die Steuerklassenänderung die Einkommenssituation wesentlich beeinflusst und bspw. man dann nicht auf das Jobcenter angewiesen ist.
Es kann aber auch gut sein, dass die Nachbeurkundung zum schnelleren Ergebnis führt als mit der Behörde zu streiten.