Географические названия в сочетании с родовым словом обычно не склоняются, если внешняя форма названия соответствует форме множественного числа: из города Помпеи (ср.: из города Мытищи).
Вы правы. Верно: в городе Костомукше (как в городе Москве). Это склоняемое название.
Правила склонения названий с сокращением г. соответствуют правилам склонения названий со словом город. Поскольку разные специалисты дают разные рекомендации для названий вроде Старый Оскол (подробнее см. в "Письмовнике"), следует сделать вывод, что допустимы и склоняемый, и несклоняемый вариант.
Правильнее: в Москве (очевидно, что речь идет о городе).
См. «Горячие вопросы».
Корректно: в городе Павловском Посаде. См. «Письмовник».
Верно: в городе Уфе.
Нормативно склонение: в городе Ульяновске.
