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

Верно: (приехать) из Москвы.

Корректно: мэр Москвы, мэр города Москвы.

От официального названия Департамент здравоохранения возможно образование сложносокращенного слова Депздрав, поэтому сочетание Депздрав Москвы орфографически корректно. Однако официальным сокращенным названием, как, например, Минюст, Минтранс, это сочетание не является. От описательного оборота департамент здравоохранения образуется нарицательное слово депздрав (ср.: колхоз, исполком). Употребление оборота депздрав Москвы в качестве неофициального обозначения организации возможно. 

Правильно: из интервью (кого-то) «Эху Москвы». Но: из интервью (кого-то) радиостанции «Эхо Москвы».

Правильно: пол православной Москвы.

Литературная норма: Я из Москвы.

Правильно: в такси, следовавшем из Москвы (предложный падеж: в такси каком?). Ср.: с такси, следовавшим из Москвы (творительный падеж: с такси каким?).

Правильно: в общественно-политической жизни.