Дано: наличие украинского паспорта с крымской пропиской и наличие официального брака со свидетельством и сменой фамилии. Надо: новый загранпаспорт.
Порядок действий : найти и связаться в Украине с фирмами-посредниками, которые за вознаграждение (оплату своих услуг) предоставляют прописку на любой подконтрольной территории (зависит от фирмы и ее филиалов, чаще всего это в Киеве) . Сейчас прописка на новом месте автоматом совершает и выписку с предыдущего места прописки, что снимает необходимость ехать в Крым и с чем-то там разбираться. На основании новой прописки можно подавать документы на новый украинский гражданский (внутренний) паспорт по месту этой самой новой прописки. С учетом того, что сам паспорт, скорее всего, выдавался в Крыму, процесс выдачи нового паспорта может затянуться, что стоит учесть.
Новый паспорт будет в виде карточки, в нем прописываются имя и фамилия на украинском и латинском, поэтому внимательно нужно смотреть, что заполнено в анкете при подаче документов, чтоб не получить фамилию с ошибками. К новому паспорту не забыть забрать (истребывается отдельно) справку о прописке (так называемая довидка номер 15). Она может понадобиться, потому что придеться и выписываться и тогда дадут новую справку о выписке (довидка номер 16). Ехать обратно в Германию и подавать пакет документов уже на новый загранпаспорт на основании поменянного внутреннего гражданского. Не забыть попросить оставить старый загранпаспорт на руках (заявление написать).