Интересно, какое консульство так паясничает? В лучшем случае Вами там занимался человек, плохо понимающий в консульских делах.

Дело в том, что поставив Вам в паспорт печать "Для проживания за границе", ОВИР поступил совершенно правильно, когда забрал ЛУ. Именно на его основе они и поставили эту печать. Понятно также, почему никто не хочет выдавать Вам новый ЛУ - печать то уже стоит!
На сайте Посольства в Берлине написана полная правда: указанного штанмпа в загранпаспорте ДОСТАТОЧНО для постановки Вас на постоянный консульский учет, листок убытия не нужен вовсе. Более того, Ваша ситуация - это как раз классический правильный способ оформления выезда на ПМЖ и последующей постановки на консучет. Все остальные (по предъявлении в консульство ЛУ или вообще оформление снятия с регистрации в России через консульство - вторичны.
Требуйте письменного отказа в постановке на КУ. Дадут или нет, в любом случае пишите заявление на руководителя консульского учреждения или на посла России в Германии. Дело абсолютно верное. Жаль только, что Вы потратили столько времени и нервов по вине этих дилетантов от консульства.