В справочных изданиях, посвященных вопросам практической стилистики, указывается, что названия городов, сел, деревень, поселков, усадеб, выраженные склоняемым существительным, как правило, согласуются в падеже с определяемым словом, например: в городе Москве, у города Смоленска, над городом Саратовом; в деревню Дюевку, через хутор Подбанку, в селе Ильинском. Однако стилистические особенности текстов могут влиять на выбор вариантных форм. Как известно, в деловой речи (часто из соображений номинативной точности) топонимы могут быть употреблены в форме именительного падежа при наличии родового слова в форме косвенного падежа: в городе Москва; в деревню Дюевка; в селе Ильинское. Если после родового слова в форме множественного числа следует список топонимов, то вполне объяснимо они могут быть представлены в своей исходной форме, то есть в форме именительного падежа. При этом никаких препятстствий для сторонников склонять топонимы тоже не существует, и вариант в городах Новосибирске, Иркутске, Красноярске считать ошибочным нет оснований. Вопрос возникает другой: чем оправдана подобная лексическая комбинация, действительно ли в этом случае необходимо слово города?

Вы правы в том, что исходно это слово, конечно, является причастием. Но причастия, как мы знаем, могут переходить в прилагательные. При этом в их значении утрачивается связь с идеей процесса, а вместе с нею и способность управлять агентивным дополнением и другими распространителями, которые актуализируют идею процесса. Когда мы восклицаем Какие воспитанные дети!, нам не приходит в голову распространить воспитанные агентивным дополнением, это звучало бы странно: *Какие воспитанные няней дети! Зато причастие, перешедшее в прилагательное, приобретает способность присоединять обстоятельство степени: Это очень воспитанные дети. Как известно, это признак качественных прилагательных, причастие к этому неспособно.

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

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

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

Верно, эти сочетания не являются плеонастичными.