И тем не менее правильно: в городе Туле. А лучше просто: в Туле.

Для оформления вопроса как прямой речи здесь нет оснований. Верен второй вариант, и в нем запятая перед когда действительно не ставится, так как придаточная часть усечена до одного союзного слова (когда).

Форма доставлены — краткое страдательное причастие прошедшего времени во мн. числе им. падежа: -ы — окончание, -ен — формообразующий суффикс. В соответствии с правилами русского правописания в кратких прилагательных пишется одно н, а в полных — два. Полная форма доставленный (формообразующий суффикс -енн-) является формой глагола доставить. Для образования этой формы к глагольной основе прошедшего времени достав- присоединяется суффикс полного причастия -енн-, при этом происходит чередование губного согласного в и сочетания губного и сонанта вл в корне слова (чередования такого типа широко распространены в русском языке, особенно в глагольном формо- и словообразовании, ср.: достав-ят – доставл-ю, откорм-ят – откормл-енн-ый, выздоров-е-ть → выздоровл-ени-е и т. п.

Отдельного рассмотрения требует основа глагола достав-, так как, в зависимости от научного подхода к анализу морфемной структуры слова, в основе может как выделяться, так и не выделяться приставка до-.

При  структурно-формальном анализе выделяются узнаваемые в современном языке морфемы, поэтому в основе достав- будет выделяется приставка до-. Структурно-семантический подход, обоснованный в трудах Г. О. Винокура, опирается исключительно на реальные словообразовательные связи слов. И так как образование слова доставить в значении ‘привезти, принести и т. п. к месту назначения’ затруднительно объяснить на основе какого-либо значения глагола ставить (см. значения этого глагола, например, в «Большом толковом словаре» под ред. С. А. Кузнецова https://gramota.ru/poisk?query=ставить&mode=slovari&dicts[]=42), приставка до- сторонниками этого подхода не выделяется.

Структурно-формальный подход к морфемному членению слова предлагается в «Словаре морфем русского языка» А. И. Кузнецовой и Т. Ф. Ефремовой. Структурно-семантический подход используется в «Словообразовательном словаре русского языка» А. Н. Тихонова. Лингвисты, занимающиеся анализом и описанием морфемной и словообразовательной структуры слова, основываются на одном из этих подходов, поэтому в словарях, справочниках и учебных пособиях возникают разные варианты членения одного и того же слова на морфемы.

Структурно-формальный анализ: до- — приставка, -ставл- — корень, -ен- — суффикс, -ы — окончание.

Структурно-семантический анализ: доставл- — корень, -ен- — суффикс, -ы — окончание.

Окончание -у (-ю) принимает в предложном падеже около 150 существительных. Это окончание всегда ударное и появляется при сочетании существительных с предлогами в и на преимущественно при обозначении места. Форму на -у образуют существительные (а) мужского рода, (б) 2-го склонения, (в) неодушевленные, (г) почти всегда односложные в начальной форме (в числе неодносложных, например, берег, ветер, аэропорт), (д) почти всегда с постоянным ударением на корне в формах единственного числа (в числе отклоняющихся от этого правила, например, мост, пост, плот, угол, а также, естественно, слова с неслоговой основой в косвенных падежах — лед, рот, ров и др.). Форму предложного падежа на -у образуют в основном существительные, обозначающие пространства, но сюда же относятся некоторые слова, которые называют вещество (лед, снег, пух и др.), собрания, совокупности (полк, ряд и др.), действия, состояния, временные отрезки (бег, бой, бред, год и др.). Форма на -у при обозначении места может быть обязательна (только в лесу) или факультативна (в цехе и в цеху, в хлеве и в хлеву), при этом возможны стилистические ограничения (ср. нейтральное в отпуске и разг. в отпуску). Появление формы на -у может зависеть от значения существительного: в солдатском строю, но в общественном строе; в родном краю, но в Красноярском крае. Многие предложно-падежные сочетания, включающие форму на -у, близки к наречным или фразеологизированным выражениям: на ходу, на весу, как на духу, гнить на корню, иметь в виду и др. Списки наиболее частотных существительных, образующих форму предложного падежа на -у, приведены, например, в изданиях: Русская грамматика. Т. 1. М., 1980. С. 488–489 (§ 1182–1183); Граудина Л. К., Ицкович В. А., Катлинская Л. П. Грамматическая правильность русской речи. Стилистический словарь вариантов. М., 2001. С. 193–198. Информацию об образовании предложного падежа того или иного слова мужского рода можно почерпнуть в толковых словарях или в словарях трудностей, например в издании: Еськова Н. А. Краткий словарь трудностей русского языка. Грамматические формы. Ударение. М., 2014.

См. «Письмовник».

Верно с двумя Н.

Это союз.

Верно: в городе Москве; УМВД по г. Старый Оскол.

Запятая перед вроде не требуется.