Господа! Прошу прощения, что вмешиваюсь в вашу полемику, но хочу сообщить то, что знаю точно. Я приблизительно знаю какой бардак в российском МИДе, но в немецком полный порядок. Поэтому в компьютере у немцев против ваших данных в верхнем правом уголочке стоит два флажка - русский и немецкий, и при выезде им точно известно, что у вас два гражданства. Что стоит у русских в верхнем правом уголочке не знаю. Просто вам повезло в тот раз, когда вы въезжали в Русланд, а потом когда выезжали.
По этой простой причине вы должны оформить не отказ от российского гражданства, а утрату этого гражданства. За утрату гражданства платить вам не придётся. Судя по тому, как вы описали ситуацию у вас на это есть все предпосылки. Но это такая тягомотина, что я могу вам только посочувствовать. У меня лично всё это безобразие продолжалось почти 4 года.
Очень внимательно почитайте законодательство о гражданстве и отталкивайтесь от него. У меня получилось. Хотя это похоже было на переговоры глухого со слепым, но я своего добился. Удачи.