«Никогда не склоняли» означает всего лишь, что в семье на протяжении многих лет повторялась грамматическая ошибка (увы, правила склонения фамилий неизвестны многим носителям языка, фамилию не склоняли исключительно из-за незнания правил). Фамилия – это слово, а слова подчиняются грамматическим законам языка. Склонение мужской фамилии Романчук обязательно; настаивать на том, чтобы учитель ее не склонял, – всё равно что настаивать на том, чтобы он говорил «живу в Москва», «работаю в школа».

Если склонять фамилию о Байке, с Байком, существует опасность, что фамилия может быть искажена: в этом случае невозможно понять, какова исходная форма: Байк? Баек? Баёк? Между тем, по словам авторов «Словаря грамматических вариантов русского языка» Л. К. Граудиной, В. А. Ицковича, Л. П. Катлинской, для словоизменения фамилий «непреложным должен быть закон об абсолютной выводимости именительного падежа фамилии из ее косвенных падежей». Поэтому гласный предпочтительно сохранять: Баёка, Баёку, Баёка, с Баёком, о Баёке.

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

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

Фамилию нужно склонять.

Мужская фамилия Скидан склоняется, женская – нет. Правила просты: все мужские фамилии, оканчивающиеся на согласный, в русском языке склоняются (единственное исключение – фамилии на -ых, -их типа Черных, Долгих), это не зависит ни от происхождения фамилии, ни от места ударения в ней. Если не просклонять мужскую фамилию (например, написать: выдан Алексею Скидан), это будет грамматической ошибкой. Такие правила были всегда, просто сейчас за их выполнением стали тщательнее следить.

Вы правы. Мужскую фамилию Евсей необходимо склонять (а женская фамилия не склоняется).

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

Мы ответили Вам на вопрос «Как правильно?». Повторим: правильно склонять Вашу фамилию, ее несклонение по отношению к мужчине (например, *пришел в гости к Борсук) — такая же грамматическая ошибка, как несклонение склоняемого нарицательного существительного (например, *пришел в гости к друг). Дальше Вам решать, следовать правилу или использовать конструкции с грамматической ошибкой.

Вы процитировали параграф 149 "Справочника по правописанию и литературной правке" Д. Э. Розенталя. Вот как звучит этот параграф в редакции 2003 г.:

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

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