Старухин был настоящим кумиром для жителей Донецкой области, заработав от них ласковое прозвище Бабуся. Вместе с женой Ларисой и двумя детьми — дочерью Ларисой и сыном Виталием (названы в честь отца с матерью) — Старухин жил в элитном дворе в центре Донецка, где у них была четырехкомнатная квартира. Кроме этого, они владели дачей, в гараже стоял автомобиль «Волга». Квартира была обставлена по-современному, впрочем, как и у всех игроков «Шахтера», которых местные власти не обижали: югославская мебель, японская техника. Болельщики Старухину буквально прохода не давали — с утра до вечера в любую погоду во дворе, где жил забивной форвард, собирались футбольные фанаты. Иногда они до глубокой ночи скандировали: «Бабуся, Бабуся!» Футболист выходил на балкон и махал им рукой. В этом же дворе жил чемпион мира по боксу Ягубкин, с которым Старухин дружил. Когда они вместе появлялись на улице, их тут же обступали фанаты.
В сезоне 1977 года «Шахтер» снова вернулся на 5-е место. Он обыграл алма-атинский «Кайрат» (3:0), ереванский «Арарат» (1:0), днепропетровский «Днепр» (дважды 1:0), бакинский «Нефтчи» (1:0), львовские «Карпаты» (3:2), куйбышевские «Крылья Советов» (3:0). Пали перед ним и московское «Торпедо» (2:0), ленинградский «Зенит» (3:2). Однако больше всего у «Шахтера» было ничейных игр — целых шестнадцать, из которых семь были «сухие» (0:0).
Среди завоеванных трофеев «Шахтера» в сезоне-77 значились следующие. Их вратарь Юрий Дегтерев удостоился почетной награды журнала «Огонек» как лучший вратарь чемпионата. А также «Кубок прогресса» (за самое крутое восхождение в чемпионате) второй раз обрел прописку в Донецке (первый раз это случилось в 1975 году).
В 1978 и 1979 годах «Шахтер» вернулся в числе призеров чемпионата СССР: в сезоне-78 он занял 3-е место. Кроме этого, он вышел в финал Кубка СССР, где уступил киевскому «Динамо» 1:2, а в одной шестнадцатой финала Кубка обладателей кубков не смог пройти испанскую «Барселону», сыграв с ней первый матч 0:3, второй — 1:1. В сезоне-79 «Шахтер» был уже вторым, чего с ним еще ни разу не случалось. Вообще во время того чемпионата «Шахтер» еще никогда не был так близок к золотым медалям. Команда Виктора Носова (одного из самых титулованных тренеров «Шахтера» в его истории, который принял команду от Владимира Салькова в 1979 году) долго лидировала в чемпионате, но в итоге довольствовалась лишь «серебром».
А вот в Кубке УЕФА «Шахтер» вылетел в самом его начале — в одной тридцать второй финала, не сумев пройти французский «Монако». В первом матче дончане одержали победу 2:1 (оба мяча забил Соколовский), но в повторном уступили 0:2.
Именно в 1979 году ярко вспыхнула звезда Виталия Старухина, который стал лучшим бомбардиром первенства — забил 26 голов — и был назван лучшим футболистом сезона. Вспоминает вратарь Виктор Чанов:
«Он именно «играл головой». В прыжке видел все, включая движение вратаря. И мог в последнюю долю секунды так выкрутить голову, что ловить было бесполезно. А прыжок у Старухина выдающимся не был. Помню, играли с «Пахтакором», и Валера Яремченко в середине поля решил перевести мяч на другой фланг, но мяч у него срезался и полетел в штрафную. Никто из наших туда не побежал. А Виталий вдруг с центра поля рванул, и вот вратарь выпрыгивает с поднятыми руками, а Старухин еще выше. И пробивает его руки. Гол…»
Несмотря на тот успех в сезоне-79, в сборную СССР Старухина не позвали. Впрочем, его и раньше там не жаловали, поскольку советскую сборную в 1975–1976 годах возглавлял Валерий Лобановский, а с ним у Старухина были плохие отношения (тренер киевлян приглашал его перейти в свой клуб, но Старухин предпочел остаться в «Шахтере», чем и усугубил свою судьбу — Восток и Центр Украины всегда соперничали). Однако и последующие тренеры нашей сборной тоже в упор не видели Старухина. И даже после успеха в сезоне-79. Тогдашний тренер сборной (и московского «Спартака») Константин Бесков посчитал, что забивной форвард «Шахтера» не вписывается в тот состав, который он сконструировал. В нем в нападении играли Юрий Гаврилов («Спартак»), Владимир Казаченок («Динамо», Москва), Хорен Оганесян («Арарат», Ереван), Сергей Андреев (СКА, Ростов-на-Дону), Степан Юрчишин («Карпаты», Львов).
Впрочем, Старухина взяли в сборную Украины, которая в июле 1979 года участвовала в Спартакиаде народов СССР. Украинцы обыграли сборные РСФСР (5:1), Узбекистана (2:1), Таджикистана (3:1) и вышли в полуфинал. Однако там они уступили сборной Москвы (0:2), сыграли вничью с белорусами (0:0) и выиграли у литовцев (2:0). После чего, набрав 3 очка, вышли в финал, где в матче за 3-е место их соперниками была команда РСФСР. Успех тогда сопутствовал украинцам — 2:1.