Вы правы. Правильно здесь: где бы не побывал путешественник.  

Норма современного употребления — су́деб. Однако в этой форме ударение падает на последний слог в устойчивом выражении волею суде́б (ср. также устойчивое выражение какими судьба́ми?). Это объясняется тем, что в прошлом ударение в формах множественного числа слова судьба могло падать на окончание или на последний слог перед нулевым окончанием, чему множество примеров в художественной литературе XIX века. Ср., например, у А. С. Пушкина: И всюду страсти роковые, // И от суде́б защиты нет.

Сочетание библиотека им. А. С. Пушкина – это описательный оборот, в первом слове которого прописная буква не нужна. Однако правила орфографии допускают функционирование усеченных названий, и эта тенденция становится все более и более заметной. На наш взгляд, использование описательного оборота в качестве усеченного названия, то есть написание его с прописной буквы, допустима в официальных документах. Такую замену можно предварить комментарием: Центральная городская публичная библиотека им. А. С. Пушкина (далее – Библиотека им. А. С. Пушкина).  

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

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

Это прилагательное словарями не фиксируется. Корректно написание с одним н как исключения из правила о двух н в словах на -ованный, -еванный. Ср.: асфальтированный, балованный, маринованный, линованный, но кованый, златокованый. Написание с одним н мы встречаем и в академическом издании «Одиссеи» в переводе В. А. Жуковского:

Если мой дом меднокованый ты посетил, благородный
Царь Одиссей, то могу уповать, что препятствий не встретишь
Ныне, в отчизну от нас возвращаясь, хотя и немало
Бед испытал ты. (Песнь тринадцатая)