Hi joki!
Die Behörde hat Recht! Die Einbürgerung unter Hinnahme von Mehrstaatigkeit ist im Prinzip nur möglich, wenn der Bewerber den Grund für die Verweigerung der Entlassung nicht selbst zu vertreten hat. Da du deinen Wehrdienst nicht abgeleistet hast, hast du den Grund für die Verweigerung selbst zu vertreten.
Wenn die Entlassung von der Erfüllung der Wehrpflicht abhängig gemacht wird, gibt es eine Ausnahme, siehe § 87 Abs. 3
AuslG. Eine der Voraussetzungen dazu ist aber, dass der Bewerber noch zum Dienst in der Bundeswehr eingezogen werden kann. Mit 25 Jahren bist du dazu aber bereits zu alt, so dass diese Möglichkeit entfällt.
Du hast demnach wohl nur die Möglichkeit, den Wehrdienst abzuleisten, damit du entlassen werden kannst.
Weitere Möglichkeiten: Siehe Nr. 87.1.2.3.2.2 STAR-VwV:
Zitat:Macht der Herkunftsstaat - ohne dass die Voraussetzungen des Absatzes 3 vorliegen - die Entlassung aus der Staatsangehörigkeit von der Leistung des Wehrdienstes abhängig, so ist dies eine unzumutbare Entlassungsbedingung, wenn der Einbürgerungsbewerber .....
c) zur Ableistung des Wehrdienstes für mindestens zwei Jahre seinen Aufenthalt im Ausland nehmen müsste und in einer familiären Gemeinschaft mit seinem Ehegatten und einem minderjährigen Kind lebt
oder
Zitat:d) sich aus Gewissensgründen der Beteiligung an jeder Waffenanwendung zwischen den Staaten widersetzt und die Leistung eines Ersatzdienstes durch den Herkunftsstaat nicht ermöglicht wird.
Weitere Möglichkeit: Gegen die Ablehnung des Entlassungsantrages beim zuständigen serbischen Gericht Klage einlegen. Es gibt nämlich Urteile des obersten serbischen Verwaltungsgerichts, wonach ein Antragsteller, der seit der Geburt in D lebt, auch ohne Erfüllung der Wehrpflicht entlassen werden kann. Allerdings sind diese Urteile schon einige Jahre alt, ich kann daher die Erfolgaussichten nicht einschätzen.