Какие нормы склонения фамилий действуют в украинском языке, мы не знаем (этот вопрос Вы можете задать нашим украинским коллегам). Но по нормам русского языка мужская фамилия Дзюб склоняется. Это отнюдь не «новые правила»: если в других документах на русском языке фамилию не склоняли, объяснить это можно только неграмотностью сотрудников, выдававших документы.
Фамилии на -ых, -их – единственное исключение. Все остальные мужские фамилии на согласный (независимо от их происхождения) склоняются – это закон русской грамматики.
Все фамилии, кончающиеся на неударное а после согласных, склоняются по первому склонению: Рибера — Риберы, Рибере, Риберу, Риберой, Сенека — Сенеки и т. д.; так же склоняются Кафка, Спиноза, Сметана, Петрарка, Куросава, Глинка, Дейнека, Гулыга, Олеша, Нагнибеда, Окуджава и др. Все такие фамилии, независимо от происхождения, являются морфологически членимыми в русском языке, т. е. в них выделяется окончание -а. Склонение фамилий, оканчивающихся в исходной форме на гласные, не зависит от того, мужские они или женские.
Женская фамилия Кравец не склоняется, мужская склоняется. Возможно два варианта склонения: Кравеца, Кравецу, Кравеца, Кравецем, о Кравеце или Кравца, Кравцу, Кравца, Кравцом, о Кравце. Ввиду того, что фамилии выполняют юридическую функцию, предпочтительно склонять их без выпадения гласного, то есть использовать первый ряд форм. Правила склонения фамилий на согласную можно прочитать в «Словаре собственных имен русского языка» Ф. Л. Агеенко (пп. 4.1–4.3). Вопрос о действительности документов, в которых фамилия записана в неправильной форме, нужно задать юристам.
Действительно, Ё пишется в обеих частях названия: Хорошёво-Мнёвники.
По одной из версий, название села Хорошёва возникло от мужского имени Хорош, по другой – от слова хорошо. Принцип, по которому при историческом образовании географических названий и, например, фамилий фиксировался тот или иной вариант ударения, определить затруднительно.
Что касается выбора между О и Ё, то в русских названиях, как и фамилиях, на шипящий + -ов (-ёв) пишется О или Ё в соответствии с традицией и с регистрацией в официальных документах.
Название склоняется и при наличии родового слова город (г.): в г. Владивостоке.
Что касается необходимости родового слова: А. Э. Мильчин и Л. К. Чельцова в «Справочнике издателя и автора» отмечают, что «сокращение г. (город), как и полное слово, рекомендуется употреблять ограниченно, главным образом перед названиями городов, образованными от фамилий (г. Киров)».
Таким образом, правильно и общеупотребительно: во Владивостоке. А варианты в г. Владивостоке, в городе Владивостоке следует характеризовать как специфически канцелярские (т. е. употребительные преимущественно в официально-деловой речи).
Исключения «придумывает» язык. Фамилии на -ых (-их) типа Золотых, Седых, Долгих являются единственным исключением из правила, гласящего, что склоняются все мужские фамилии, оканчивающиеся на согласный звук. Эти фамилии несклоняемы, потому что они в каком-то смысле уникальны: они происходят от формы родительного (и предложного) падежа множественного числа имен прилагательных. В этом их принципиальное отличие от фамилий на -ич, -ец, -чик и т. п., которые могут и должны склоняться. Самостоятельно объявить свою фамилию несклоняемой вопреки законам русской грамматики нельзя.
Ваша фамилия исключением не является. Фамилии на -ых (-их) типа Золотых, Черных, Долгих являются единственным исключением из правила, гласящего, что склоняются все мужские фамилии, оканчивающиеся на согласный звук. Эти фамилии несклоняемы, потому что они в каком-то смысле уникальны: они происходят от формы родительного (и предложного) падежа множественного числа имен прилагательных (ср.: золотых куполов, долгих проводов). Склонение Вашей фамилии определяется именно тем правилом, которое Вы привели в вопросе.
Вы абсолютно правы. Действительно, на письме часто не различают двойную фамилию и соединение двух фамилий, принадлежащих разным людям, хотя дефис и тире такую возможность нам дают, ср.: законы Гей-Люссака, закон Вант-Гоффа и закон Джоуля — Ленца, уравнение Навье — Стокса, комета Шумейкеров — Леви 9, комета Шайн — Шалдеха. Некоторые подобные названия по фамилиям ученых закреплены в академическом орфографическом словаре, а правило сформулировано, например, в академическом справочнике «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина (М., 2006 и след.).
Корректно написание со строчной.
Имена прилагательные, образованные от личных имен и фамилий при помощи суффиксов -ск-, -овск- (-евск-), -инск-, пишутся со строчной буквы, напр.: далевский словарь, дарвиновское учение, бетховенская соната, шекспировские трагедии, пришвинская проза, пушкинская гармония, суворовские традиции. Однако с прописной буквы пишутся имена прилагательные на -ский, входящие в состав наименований — имен собственных, в том числе имеющие значение «имени того-то», «памяти того-то», напр.: Габсбургская династия, Петровские реформы, Строгановское училище, Нобелевская премия, Ломоносовские чтения, Булгаковская конференция, Вахтанговский театр, Королевский Шекспировский театр (в Англии).
Это чрезвычайно сложный вопрос. В справочниках Д. Э. Розенталя указано, что из фамилий на ударяемые -а склоняются только славянские: у писателя Майбороды, к философу Сковороде, фильмы Александра Митты, но романы Золя, Дюма.
Тогда как в приложении к "Словарю русских личных имен" А. В. Суперанской, изданном в более позднюю эпоху, говорится, что и мужские, и женские нестандартные русские и нерусские фамилии, оканчивающиеся на -а, -я, как ударное, так и неударное, склоняются (исключением служат только французские фамилии с ударением на последнем слоге).
