Скажем, сегодня Петропавловская крепость находится в Санкт-Петербурге, Россия

Ну хоть универсальный алгоритм выяснения правильного названия и административной принадлежности определенной территории в определенный момент времени существует?

В ХХ в. в России (в пределах РФ) изменили названия 129 городов. До ХХ в. из сохранивших до нашего времени городской статус поселений меняли названия 42.
При образовании из сельских поселений разного типа (села, слободы, заводы, местечки, погосты и т. д.) претерпели изменения названий 123 города (в том числе 16 на Южном Сахалине).
Закрытые административно-территориальные образования (ЗАТО) при переводе из «нелегального» состояния в официальное, когда их стали показывать на картах и включать в статистические справочники с 1995 г., получили вместо «номерных» обозначений (Арзамас-16, Голицыно-2, Свердловск-44, Свердловск-45, Томск-7 и др.) цивильные имена 19 городов.
Кроме того, 10 городов, вошедших в состав более крупных центров, так же переименовывались (Царское Село сперва получило название Детское Село, а в 1937 г. — Пушкин; Петергоф с 1944 г. именовался Петродворцом, Сарепта — Красноармейском, Бежица была Орджоникидзеградом и т. д.).
Число переименований превышало число переименованных городов, так как некоторым городам меняли названия по несколько раз. Существует значительная группа городов с особенно неустойчивыми названиями. Среди них Владикавказ (Владикавказ — Орджоникидзе — Дзауджикау — Орджоникидзе — Владикавказ), Рыбинск (Рыбинск — Щербаков — Рыбинск — Андропов — Рыбинск), Шлиссельбург (Орешек — Нотебург — Шлиссельбург — Петрокрепость — Шлиссельбург), Лиски, Серов, Черкесск, Карачаевск, Белогорск, Буденновск, Уссурийск, Приозерск, Новокузнецк и др.
Переименованиями были охвачены самые разные города — от крохотного Лихвина (ныне Чекалин) до огромного Санкт-Петербурга. Доля переименованных городов выше у крупных центров. Претерпели переименования половина городов-миллионеров, 40% крупнейших, 20% крупных и больших и только 8—9% малых и средних городов. Среди главных городов субъектов РФ изменили название 30, или 34% общего числа, городов этой категории.
В целом, если считать и города, изменившие свои названия при образовании, почти 400 городов на территории РФ меняли свои названия. Это составляет примерно 35% всех городов страны.

Переименования в ряде случаев принимали характер топонимической чехарды: старое имя заменялось новым, затем возвращалось историческое название, вновь давалось новое имя (уже другое) и опять восстанавливалось первоначальное. Вот пример, помимо уже приведенных раньше. Надеждинск (первоначально — Надеждинский завод) получил городские права в 1926 г. В 1934 г. переименован в Кабаковск (по имени тогдашнего первого секретаря обкома партии). После того как Кабаков был репрессирован, город в 1937 г. вновь стал Надеждинском. В 1939 г. назван Серовом в честь летчика Анатолия Серова, заслужившего звание Героя Советского Союза в небе Испании.
В 1926 г. село Александровское было преобразовано в город Александровск. В 1931 г. его переименовали в Краснопартизанск, а в 1936 г. в Куйбышевку-Восточную. В 1957 г. город получил нынешнее название Белогорск. Вследствие административно-топонимического зуда население еще не успевало привыкнуть к одному имени, как на смену ему приходило другое.
Переименованию подвергались города не только старые, но и новостройки. Хибиногорск стал Кировском, Калининград (Московской области) — Королевом. Закрытый Арзамас-16 явился миру как Кремлев, но затем получил имя Саров. Крупнейший центр строительства атомных подводных лодок Молотовск (образованный из поселка Судострой) стал Северодвинском. Желание иметь городское имя привело к замене названия Лаптево на Ясногорск, Чесноковка стала Новоалтайском.

Просто поднимаются официальные сайты определённых территорий или соответствующих им госорганов. Как правило, информация там есть.