Отказался и Андрей Миронов, раздосадованный тем, что публика считала его лучшей ролью сыгранного им в «Бриллиантовой руке» Гешу Козодоева. Гайдай попробовал еще нескольких актеров и в итоге остановился на молодом ленинградском актере Сергее Мигицко. Городничего сыграл Анатолий Папанов, его жену – Нонна Мордюкова, хотя на нее пробовалась и Наталья Гундарева. В фильме также снялись Сергей Филиппов, Станислав Чекан, Вячеслав Невинный, Валерий Носик, Михаил Кокшенов, Олег Анофриев, Леонид Харитонов и Анатолий Кузнецов. Уездного лекаря Гибнера сыграл Александр Ширвиндт. Он же прочитал дикторский текст. Оператором был снова Сергей Полуянов, композитором, что предсказуемо, Александр Зацепин, ну и художником – Евгений Куманьков.
Работа над фильмом с самого начала оказалась под пристальным надзором Госкино. Для съемок был построен комплекс декораций, включавший дом городничего и других персонажей, а также присутственные места. Они были решены режиссером, художником и оператором в различных оттенках светлых тонов. Мне рассказывал художник-декоратор Владимир Фабриков, что это вызвало грозный окрик Госкино: «Вы что, не знаете, что царская Россия была „темным царством“»? Декорации еще до строительства потребовали окрасить в темные тона, что сразу задало мрачное настроение происходящих в них событий и утяжелило восприятие фильма.
Недовольство вызвало и остроумие, как гоголевское, так и гайдаевское, в результате чего многие блестящие выражения были безжалостно вырезаны. Особенно усердствовал в этом тогдашний главред Госкино – Даль Орлов. Великую авторскую реплику «На зеркало неча пенять, коли рожа крива», которую не стал убирать из гоголевского текста даже император Николай I, не отличавшийся либерализмом Филипп Ермаш категорически потребовал изъять из фильма. Гайдай сопротивлялся как мог, спорил, конфликтовал, упирался. Фильм после множества переделок все же приняли, но присвоили ему третью категорию и в несколько раз сократили количество копий для проката. Возможно, судьбу картины мог изменить, как в случае с «Бриллиантовой рукой», показ на правительственных дачах (Брежнев любил фильмы Гайдая), но фильм снимался на 70‐миллиметровой пленке, для которой требовались широкоформатные проекторы, имевшиеся только в самых новых кинотеатрах. Члены Политбюро в кинотеатры не ходили. Это также повлияло на результаты проката.
Критики стали дружно утверждать, что Гайдай кончился, талант его иссяк, а зрители его кино разлюбили. Но в руководстве «Мосфильма» к Гайдаю относились доброжелательно, и ему предложили сделать совместную постановку с Финляндией по повести финского классика Майю Лассилы «За спичками», переведенную на русский язык Михаилом Зощенко. Сценарий написали Гайдай с Бахновым, оператором был Сергей Полуянов, художником Феликс Ясюкевич, композитором Александр Зацепин. На главную роль изначально был утвержден Евгений Леонов, его кандидатуру горячо поддержали финны. На вторую главную пробовались Леонид Куравлев, Вячеслав Невинный и популярный в балтийских странах Донатас Банионис. Гайдай утвердил Невинного. В фильме также снялись Галина Польских, Нина Гребешкова, Сергей Филиппов, Михаил Пуговкин и несколько финских актеров и актрис. Фильм должен был учитывать специфику тамошнего юмора, далеко не всегда совпадавшего с отечественным. Премьера состоялась в октябре 1980 года. Фильм по итогам года занял одиннадцатое место, собрав в прокате примерно столько же, сколько и «Двенадцать стульев».
В 1981 году Гайдай начал работу над фильмом «Спортлото-1982». Снова сценарий (на этот раз оригинальный) написали Гайдай и Бахнов. Это была насыщенная приключениями история поиска потерянного выигрышного билета всесоюзной лотереи. Сергею Полуянову за камерой помогал Виталий Абрамов, художником был Феликс Ясюкевич, музыку писал вечный Зацепин. В главных ролях снялись совсем молодые Альгис Арлаускас, Светлана Аманова и Денис Кмит. Компанию им составили гайдаевские актеры Нина Гребешкова, Михаил Пуговкин, Сергей Филиппов, Михаил Кокшенов. Впервые у Гайдая снялся Борислав Брондуков. Съемки проходили в Крыму. Картина стала одной из последних успешных работ Гайдая. Ее посмотрели 55 миллионов зрителей, а критики на этот раз сочли фильм откровенной неудачей. Молодого героя назвали попыткой режиссера реанимировать в новых условиях образ Шурика, упрекали в огрехах вкуса, перечисляли самоповторы и самоцитаты.