Наступил 1996-й, но денег все еще не было. Рязанов, однако, не сомневался в том, что картина состоится, хотя ему требовалось предварительно разжиться не только бюджетом, но и свободным временем. Контракт с «РЕН ТВ» обязывал Эльдара Александровича ежемесячно предоставлять для эфира две новые программы. Дабы освободить восемь-девять месяцев для работы над будущим фильмом, надлежало единовременно снять шестнадцать-восемнадцать таких программ. Именно в связи с этой необходимостью родился вышеупомянутый цикл «Парижские тайны Эльдара Рязанова».

В январе возглавляемая Эльдаром Александровичем телевизионная съемочная группа вылетела в двадцатидневную парижскую командировку. За эти две декады Рязанов совершил настоящий журналистский подвиг, успев отснять материал для четырнадцати передач.

Цикл продолжился и в дальнейшем — последние новые передачи вышли в эфир в 1998 году. Героями и собеседниками Рязанова были Жан Маре, Роман Поланский, Роже Вадим, Шарль Азнавур, Клод Лелуш, Анни Жирардо, Филипп Нуаре, Анук Эме, Пьер Ришар, Марина Влади, Брижит Бардо, Изабель Юппер, Клаудиа Кардинале, Робер Оссейн, Жан Поль Бельмондо и другие.

Весной 1996 года Госкино наконец разжилось кое-какими средствами из казны — и Рязанову был выделен бюджет на производство фильма, хотя и максимально скудный. Предстояло выкручиваться.

Сценарий, как почти всегда у Рязанова, писался в расчете на конкретных исполнителей: на роль Ксении режиссер планировал вновь выписать из Франции полюбившуюся ему Ирен Жакоб, а на Каблукова утвердить Олега Меньшикова. Один из наиболее звездных российских актеров 1990-х, Меньшиков уже «слегка» работал с Рязановым — в «Дорогой Елене Сергеевне» озвучивал роль персонажа, сыгранного Андреем Тихомирновым. Успел Олег дать и предварительное согласие стать «дуралеем», но к тому времени, когда Рязанов обзавелся бюджетом, актер уже участвовал в других проектах.

Тут-то и возникла кандидатура знаменитого клоуна и основателя театра «Лицедеи» Вячеслава Полунина, который имел минимальный опыт работы в кино и соглашаться на крупные роли дотоле не решался. «Я последние лет десять изучаю кино очень основательно, — сообщал Полунин в интервью журналу „Киносценарии“, когда еще шли съемки „Дуралеев“. — У меня дома коллекция кино комического, я знаю наизусть все сцены, принципы и так далее. Но я считаю, что я еще не готов, нужно еще какое-то время, чтобы я был готов. А тут вдруг неожиданно, до того, как я стал готов, Эльдар Александрович сказал: „Хочешь попробовать у меня?“ Естественно, я ему сказал, что даже если есть один процент, что я подойду, я тут же приеду, попробую. Я не рассчитывал совершенно, это было нереально.

Во-первых, это все-таки далеко: то, что я делаю, — и то, что он, потому что это разговорное кино, а я вообще не разговариваю. Для меня это огромный континент, который я сейчас только изучаю, хочу понять, как пользоваться словом и т. д. А с другой стороны, мы совершенно совпадаем, один в один, — то, что он делает, и то, что я, — это трагикомедия.

То, что он делает в кино, — идеально, я обожаю все его фильмы, все книги знаю до каждой странички. Его линия в кино, где трагическое и смешное, все, сливаясь в единый сплав, обрушивается на персонажей, которые недотепы недоделанные, то есть неполучившиеся люди, и они оказываются вдруг счастливыми, это очень близко мне. Поэтому, с одной стороны, я полностью понимаю, что не совпадаю по технике, а с другой стороны, это чуть ли не единственный режиссер, у которого я очень хотел бы сниматься».

Уже на первых кинопробах Полунин разыгрывал любовную сцену с Татьяной Друбич, которая давно нравилась Рязанову и по ролям в картинах Сергея Соловьева, и по мимолетному личному общению на «Мосфильме».