Дмитрий, здравствуйте. Если речь о замене российского водительского удостоверения гражданину РФ, отсутствие отметки о регистрации в паспорте само по себе не мешает замене. Ждать три недели только ради «прописки» не требуется.
Основная ссылка — пункт 3 Правил, утверждённых постановлением Правительства РФ от 24.10.2014 № 1097: водительские удостоверения выдают по месту обращения. Замена из-за изменения фамилии предусмотрена подпунктом «б» пункта 29 и производится без экзаменов.
Уточню важный момент в первом ответе коллеги: при замене только из-за фамилии медицинское заключение не обязательно. Подпункт «в» пункта 30 прямо позволяет представить его по желанию. Без него прежний срок действия удостоверения сохраняется; с медицинским заключением новое удостоверение, по общему правилу, выдают на десять лет — пункт 32. Если одновременно истёк срок действия, ситуация со справкой будет другой.
Подайте заявление на замену, приложите новый паспорт, прежнее удостоверение при наличии и необходимые сведения о СНИЛС. Возьмите документ о смене фамилии, чтобы связать старые и новые данные. Госпошлину оплачивают в установленном порядке.
Можно использовать такую формулировку:
«Прошу заменить российское национальное водительское удостоверение в связи с изменением персональных данных. На основании пункта 3 Правил, утверждённых постановлением Правительства РФ № 1097, обращаюсь по месту фактического нахождения. Прошу при наличии оснований для отказа выдать мотивированное письменное решение».
Устное «не знаем, как оформить» — ещё не решение по вашему заявлению. Если документы не принимают именно из-за отсутствия регистрации, зафиксируйте подразделение, дату и причину отказа и обратитесь с жалобой к руководителю подразделения либо в вышестоящий орган МВД.
И не откладывайте замену: после изменения фамилии прежнее удостоверение считается недействительным по подпункту «б» пункта 35. Новый паспорт вместе со старой карточкой это не исправляет.
Если хотите, можем продолжить здесь и подготовить короткое обращение под вашу ситуацию, чтобы в МРЭО обсуждали конкретную норму, а не наличие штампа.