韓国に出生届けを出していない人の日本人男性と国際結婚する場合

韓国籍で永住権を持っている者です。
父が在日韓国人で母は日本人ですが、両親とも離婚しており、いないため自分でやるしかない状況です。
帰化しようと母が25年以上前に、弁護士さんに依頼し調べてもらったところ私は韓国には出生届けが出ていなく存在しない人になっていて、どうしようもないと言われ韓国籍のまま永住権を取ってずっといます。

日本の方と、今年結婚したく最寄りの役所に問い合わせし出生届け記載事項証明書を提出するよう言われました。

出生届けを出したと思われる役所に請求しましたがないと言われ、地方法務局に聞いてほしいと言われ法務局に連絡しました。
日本で出生届けを出した後に、父が勝手に韓国に変えてしまい母の戸籍の私の名前は✕がついており、その事を説明すると27年間の保存期間を過ぎると処分する為ないので最寄りの役所に説明してと言われました。
今住んでいる市役所に、その事を話し婚姻するにはなんの書類がいるか聞きましたが、
あなたが本当にあなたである証明書がないのでまず婚姻は認められない。
帰化も難しいのでは?
役所に来て話はできるが、レアな件なので具体的な解決方法はないと思う。
と言われました。

父親が自分の都合のいいように勝手に国籍を変えられ中途半端な状態にされ、どこに相談しても無理と言われ私は、結婚することも帰化することもできないのでしょうか?

専門ではないですが、法務局と協議して、出生届記載事項
証明書に代わる判決が必要ならどのような判決をとれば
いいのか、教えてくれるか調査してもらうといいですね。
また行政書士で専門の方がいそうなので、探して聞いても
いいですね。