Да, на его поиски является обстоятельством цели, в город Альмерию – обстоятельством места.

В современном русском письме такие написания не приняты. Корректно писать просто город Москва. Обозначить в документе тождество развернутого и краткого наименования можно с помощью конструкции: город федерального значения, административный центр Центрального федерального округа и центр Московской ...Москва (далее — город Москва).

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

Корректор прав. Кемерово – существительное среднего рода. Если существительное обозначает географический объект, то его род определяется родом слова, которое обозначает тип объекта (город, река, озеро и т. д.) – такое правило, действительно, существует, но касается только несклоняемых существительных (Тбилиси мужского рода, так как это город, Миссисипи женского рода, так как это река). Кемерово – изменяемое слово (в Кемерове, из Кемерова). Ср.: Москва – слово женского рода, хотя это тоже город.

Употребление слова город (и сокращения г.) перед названием города – характерная черта канцелярской речи, поэтому в «Справочнике издателя и автора» А. Э. Мильчина, Л. К. Чельцовой дана рекомендация употреблять сокращение г. (и полное слово город) ограниченно, преимущественно перед названиями городов, совпадающими с фамилиями людей, напр. г. Пушкин, г. Королев. Однако на практике эта рекомендация редко соблюдается,  сокращение г. и полное слово город употребляют перед названиями всех городов.

В русском языке порядок членов предложения свободный. Верны все варианты, которые Вы перечислили.

Правила Вы можете посмотреть в Полном академическом справочнике под ред. В. В. Лопатина.

В приведенных Вами предложениях знаки нужно расставить следующим образом. 

1. И хотя было уже поздно, я решил остаться. И когда взошло солнце, никто уже не спал. В начале предложения между союзом и и подчинительным союзом запятая не ставится. 

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

Независимо от того, средствами какой графики записано предложение, оно остаётся английским предложением, в котором имеются все необходимые члены английского предложения. Искать в нем русские подлежащее, сказуемое и т. д. бессмысленно. С точки зрения грамматики русского языка это просто некая последовательность букв, не более.

Очевидно, обстоятельства для решения вопроса и в целях безопасности относятся к разным аспектам ситуации: для решения вопроса относится к самому факту связи, то есть к сочетанию потребуется связаться с вами, а в целях безопасности — к способу, с помощью которого осуществится связь, то есть к сочетанию по видеозвонку. В таком случае предложение лучше отредактировать. Если редактирование по каким-то причинам невозможно, то допустимо обособить второе обстоятельство: Для решения вопроса, в целях безопасности, потребуется связаться с Вами по видеозвонку.
Предложение допускает и иные варианты толкования, предполагающие иные варианты редактирования; для полного понимания нужен контекст.