1. Криминальный и дорогой. Можно сделать дубликат номеров.
то что украли оба номера, это плохо. если бы один остался, договориться за разумное вознаграждение, что бы вам сделали один номер вполне возможно (если вы поищите яндексом, или сразу на авто.ру, вы найдете пару фирм, которые вам с этим помогли бы).
два номера вам либо вообще не сделают, либо сделают задорого.
и если ваши старые номера где-то всплывут, то сами понимаете...

2. Вы можете совершенно спокойно ездить без номеров.
Штраф за это - предупреждение (т.е. бесплатно) или 0.5 МРОТ. Никаких санкций в виде эвакуации и т.п. не предусмотрено (цитировать КОАП я не буду, не поленитесь купить его (а заодно и новую редакцию ПДД) и почитать на досуге, это очень полезно). Более того, останавливать вас будут гораздо реже, чем когда вы ездили с номерами.
Про неприятности в другом городе, это вообще полная пурга, лейтенант-недоучка сказал вам подобный бред. КОАП действует одинково на всей территории РФ, и наказание за езду без номеров в любом городе и деревне одно и тоже. Даже если вдруг местные власти примут решение скажем эвакуировать машины без номеров (что само по себе бред), это будет совершенно незаконно. А справка, которую вам дали ничего не значит, и от уплаты штрафа за езду без номеров не освобождает. Т.к. ни ПДД, ни КОАП не предусматривают возможность езды без номеров, но со справкой

Эта справка вам нужна только при получении новых номеров в вашем городе. И с тем же успехом вы можете получить такую справку в вашем родном городе.

Небольшое лирическое отступление (если лень, можете не читать)
Если вас все таки остановили за нарушение, или просто езду без номеров, то при хорошем знании КОАП вы можете вообще избежать как составления протокола, так и дачи гайцу взятки (не устаю удивляться, как за нарушение, за которые предусмотрено 50 руб штрафа, некоторые упорно дают гайцам 100 руб

)
Достаточно грамотно изложить гайцу про статьи 28.6, и 32.2/3 КОАП и потребовать уплаты штрафа на месте (в КОАП есть дырка по принятию на месте штрафов до 1 МРОТ за нарушения ПДД), а в случае отказа пригрозить гражданским иском по факту нарушения ваших прав и свобод, как в 99.99% случаев вам отдадут документы и пожелают счастливого пути (все общение на эту тему занимает не более пары минут). Но для этого надо действительно хорошо знать КОАП и другие законы (среди моих близких знакомых есть только один человек, который может успешно действовать по этой схеме), в противном случае вас разведут как кролика, в результате отдадите денег только больше (если интересно, могу рассказать случай из жизни, как один знакомый решил блеснуть перед гайцем знанием законов, в результате попал на $50

)

Если вам лень читать КОАП, и вообще не унизительно давать гайцам деньги, то можете плюнуть на знание законов, и просто давать 50 руб каждому остановившему вас гайцу

3. Законный и очевидный.
Едете в свой город, снимаете машину с учета, ставите ее в Москве на знакомого.
Я бы рекомендовал бы пока ездить без номеров, а при первой возможности поехать и снять с учета. Подумайте, что будет, если (не дай Бог!) у вас украдут документы на машину. Вот тогда вы помучаетесь гораздо сильней, чем с номерами...
Только пожалуйста, пока будете ездить без номеров, не показывайте гайцам вашу справку

Если будут спрашивать почему без номеров, можете отвечать что угодно, что "забыл дома"

, а можете честно говорить, что украли. на величину наказания это никак не повлияет