Я только что вернулся из России (Москва), был в паспортном столе по этому вопросу.
Итог:
1. Занимаются этими вопросами только начальники паспортных столов (ПВО) лично.
2. Заявление пишется только от руки, на компьютере нельзя.
3. В заявлении должен быть указан или точный адрес в Германии, или "для последующей постановки на учет в консульстве в городе таком-то, ФРГ".
4. Заявление заверяется в ЕГРЦ (т.е. ЖЭКе) и отдается начальнику ПВО, он выписывает в течение 3 рабочих дней.
5. При выписке во внутренний паспорт ставят штамп и дают листок убытия. Новый ЗП делать не надо. Сначала мне пытались в ПВО компостировать мозги, что нужен новый ЗП на ПМЖ, однако после звонка в РУВД и последующим звонком из РУВД в ПВО необходимость в этом резко отпала.
6. Личная явка обязательна. Однако моя знакомая, занимавшаяся недавно в Питере тем же вопросом, нашла человека, занимающегося недвижимостью, у которого есть связи с начальником ПВО, и по такому знакомству можно за определенную мзду выписаться и без личной явки за 5 минут. Т.е. опять же все чисто по-русски. Вывод: ищите блат, готовьте деньги, тогда можно туда и не ехать.