Какие нормы склонения фамилий действуют в украинском языке, мы не знаем (этот вопрос Вы можете задать нашим украинским коллегам). Но по нормам русского языка мужская фамилия Дзюб склоняется. Это отнюдь не «новые правила»: если в других документах на русском языке фамилию не склоняли, объяснить это можно только неграмотностью сотрудников, выдававших документы.

Фамилии на -ых, -их – единственное исключение. Все остальные мужские фамилии на согласный (независимо от их происхождения) склоняются – это закон русской грамматики.

Все фамилии, кончающиеся на неударное а после согласных, склоняются по первому склонению: Рибера — Риберы, Рибере, Риберу, Риберой, Сенека — Сенеки и т. д.; так же склоняются Кафка, Спиноза, Сметана, Петрарка, Куросава, Глинка, Дейнека, Гулыга, Олеша, Нагнибеда, Окуджава и др. Все такие фамилии, независимо от происхождения, являются морфологически членимыми в русском языке, т. е. в них выделяется окончание -а. Склонение фамилий, оканчивающихся в исходной форме на гласные, не зависит от того, мужские они или женские.

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

• Названия людей по национальности и по принадлежности к воинским соединениям, преимущественно употребляющиеся в формах множественного числа в собирательном значении: мадьяры - мадьяр, туркмены - туркмен, гардемарины - гардемаринов и гардемарин, партизаны - партизан, солдаты - солдат; сюда же относится форма р. п. мн. ч. человек.
• Названия парных предметов: ботинки - ботинок, глаза - глаз, манжеты - манжет, погоны - погон, чулки - чулок, эполеты - эполет, сапоги - сапог.
• Названия мер и единиц измерения: 220 вольт, 1000 ватт, 5 ампер, 500 гигабайт. Если же такие названия употребляются вне "измерительного" контекста (иначе говоря, форма родительного падежа не является счетной), то используется окончание -ов: жить без избыточных килограммов, не хватает гигабайтов.

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

Для некоторых существительных образование форм мн. ч. род. п. затруднено; это слова мечта, мольба, башка. Напротив, слова щец и дровец не имеют других форм, кроме формы мн. ч. род. падежа.

См.: "Русская грамматика", М., 1980.

Слово динозавр входит в целую группу названий животных, которые используются в переносном значении по отношению к людям, обладающим высоким профессиональным уровнем. Это слова акула, зубр, кит, мастодонт, монстр. Приведем несколько примеров: 

Мною занимались такие зубры эстрады, как замечательный конферансье Михаил Наумович Гаркави и даже Смирнов-Сокольский (И. Кио).

[На конкурс] подавались монстры, зубры и прочие мастодонты от украинского кино (из блогов).

Перед ними был настоящий динозавр отечественного кинематографа – сам Владимир Рудольфович Карпов, лауреат многочисленных премий (К. Казанцев).

В толковых словарях не для всех названных слов фиксируется «человеческое» значение. Отчасти это связано с тем, что оно еще находится в стадии формирования. 

У слова динозавр некоторые словари отмечают «человеческое» значение, но более старое, чем «профессионал», обусловленное тем, что динозавры – почти полностью вымерший вид животных. Например, в «Толковом словаре русской разговорной речи» (1-й том. М., 2014) предложена такая формулировка: «о человеке как представителе ушедшей эпохи, придерживающемся устаревших взглядов, ветхозаветных принципов и т. п.». Это значение уже устоялось в языке, поэтому оно будет внесено и в готовящийся сейчас 3-й том «Академического толкового словаря русского языка». А для фиксации значения «профессионал» лексикографы пока не нашли достаточных оснований. И причина не в стилистической окраске слова, в словари включаются слова из самых разных пластов языка. В поле внимания специалистов – система значений слова в их развитии, стилистические свойства, синтаксическое поведение, употребительность и многое другое. Лексикографическое решение принимается исходя из полной, всеобъемлющей информации о языковой единице.

Ответить на Ваш вопрос нам помог лексикограф – кандидат филологических наук научный сотрудник Института русского языка им. В. В. Виноградова РАН Анна Разифовна Пестова. Именно она (без страха) занималась изучением монстров, зубров и прочих мастодонтов и предоставила нам материалы своего исследования.

Стомиллионный (в сочетании с существительным народ) — это прилагательное. Верно, что оно мотивировано составным количественным числительным, но обозначает оно признак предмета и, самое главное, не является порядковым: оно служит не для обозначения порядкового номера предмета при счете (такого количества народов на Земле нет и быть не может, как бы мы ни подсчитывали), а для выражения идеи огромности одного конкретного народа.

Если же мы говорим что-нибудь вроде Я тебе уже стомиллионный раз повторяю! — в этом случае перед нами порядковое числительное, потому подразумевается (с преувеличением, конечно), что до этого повторял(а) уже 99 999 999 раз.

В словосочетании семидесятый год перед нами порядковое числительное, оно называет порядковый номер предмета при счете (в данном случае — при счете лет). Если мы говорим В семидесятые ты еще под стол пешком ходил, то используем это слово в расширительном значении, но оно сохраняет признаки порядкового числительного.

Что касается «Русской грамматики», то нужно иметь в виду, что ее авторы ставили перед собой задачу дать максимально последовательное описание грамматического строя русского языка, что привело их к ряду решений, непривычных для человека, окончившего среднюю школу. В частности, они отказали словам, которые традиционная грамматика считала порядковыми числительными, в принадлежности к числительным — на том основании, что у этих слов нет абсолютно никаких морфологических отличий от, например, относительных прилагательных: они точно так же изменяются по родам, числам и падежам, причем имеют точно ту же систему окончаний, что и обычные прилагательные. (А вот количественные числительные имеют целый ряд морфологических отличий от существительных.) Поэтому в «РГ» отсутствует понятие порядкового числительного, зато появилось понятие порядкового прилагательного.

В формулировке вопроса непонятно, почему автор говорит о поэтах и «стихотворном материале». Разве эти слова функционируют только в поэтической речи?

Ваша фамилия исключением не является. Фамилии на -ых (-их) типа Золотых, Черных, Долгих являются единственным исключением из правила, гласящего, что склоняются все мужские фамилии, оканчивающиеся на согласный звук. Эти фамилии несклоняемы, потому что они в каком-то смысле уникальны: они происходят от формы родительного (и предложного) падежа множественного числа имен прилагательных (ср.: золотых куполов, долгих проводов). Склонение Вашей фамилии определяется именно тем правилом, которое Вы привели в вопросе.

Действительно, Ё пишется в обеих частях названия: Хорошёво-Мнёвники.

По одной из версий, название села Хорошёва возникло от мужского имени Хорош, по другой – от слова хорошо. Принцип, по которому при историческом образовании географических названий и, например, фамилий фиксировался тот или иной вариант ударения, определить затруднительно.

Что касается выбора между О и Ё, то в русских названиях, как и фамилиях, на шипящий + -ов (-ёв) пишется О или Ё в соответствии с традицией и с регистрацией в официальных документах.

Женская фамилия Кравец не склоняется, мужская склоняется. Возможно два варианта склонения: Кравеца, Кравецу, Кравеца, Кравецем, о Кравеце или Кравца, Кравцу, Кравца, Кравцом, о Кравце. Ввиду того, что фамилии выполняют юридическую функцию, предпочтительно склонять их без выпадения гласного, то есть использовать первый ряд форм. Правила склонения фамилий на согласную можно прочитать в «Словаре собственных имен русского языка» Ф. Л. Агеенко (пп. 4.1–4.3). Вопрос о действительности документов, в которых фамилия записана в неправильной форме, нужно задать юристам.

Название склоняется и при наличии родового слова город (г.): в г. Владивостоке.

Что касается необходимости родового слова: А. Э. Мильчин и Л. К. Чельцова в «Справочнике издателя и автора» отмечают, что «сокращение г. (город), как и полное слово, рекомендуется употреблять ограниченно, главным образом перед названиями городов, образованными от фамилий (г. Киров)».

Таким образом, правильно и общеупотребительно: во Владивостоке. А варианты в г. Владивостоке, в городе Владивостоке  следует характеризовать как специфически канцелярские (т. е. употребительные преимущественно в официально-деловой речи).

Исключения «придумывает» язык. Фамилии на -ых (-их) типа Золотых, Седых, Долгих являются единственным исключением из правила, гласящего, что склоняются все мужские фамилии, оканчивающиеся на согласный звук. Эти фамилии несклоняемы, потому что они в каком-то смысле уникальны: они происходят от формы родительного (и предложного) падежа множественного числа имен прилагательных. В этом их принципиальное отличие от фамилий на -ич, -ец, -чик  и т. п., которые могут и должны склоняться. Самостоятельно объявить свою фамилию несклоняемой вопреки законам русской грамматики нельзя.