Вся процедура обмена паспорта в России (ОВИР по месту жительства) происходит следующим образом:
Сначала надо заверить Internationale Heiratsurkunde апостилем (например, в Bezirksregierung).
Потом это интернациональное свидетельство обраке нужно перевести. Заверенный перевод нашему консульству до последнего времени нужен не был. Можно просто самому его перевести и распечатать.

Листок с переводом и само свидетельство отвозится в консульство и там производится его признание русской стороной (легализация). Консульство скрепляет эти два листка (св-во и перевод) и заверяет все это (по-моему, за 60 или 70 марок). В заграничном паспорте проставляется отметка о браке и смене фамилии, а также отметка о том, что паспорт подлежит обмену.
С оштемпелеванным заграничным паспортом, с заверенным, переведенным и легализованным интернациональным свидетельством о браке, а также с внутренним паспортом нужно ехать домой и там подавать все эти бумаги на обмен внутреннего и заграничного паспорта. Сначала выдают внутренний паспорт, а потом заграничный.
Проблем при этом особых у меня не возникло.
Единственное, нужно проследить за правильным написанием фамилии и имени в новом паспорте. Так как наш ОВИР применяет французкую или английскую транслитерацию, которая может полностью исказить немецкую фамилию.
ВАЖНО! С самого начала ОВИРу нужно указать на правильное написание фамилии и имени. Основанием для этого является штамп консульства, где указаны русский и немецкий вариант "оригинальной" немецкой фамилии.
ОВИР ставит свой штемпель "аннулировано" на "старый" заграничный паспорт и выдает его на руки для возвращения в Германию, так как в нем находится вид на жительство/виза.
С двумя заграничными паспортами и кучей чемоданов возвращаемся в Германию (при пересечении границы предъявляем два паспорта) и волочемся в Ausländeramt переносить визу/вид на жительство в новый паспорт (Übertragung).
Вот и вся наука. Главное - запастись временем и не нервничать.
Желаю всего хорошего!