Вы привели отличный пример того, что вводное слово не определяется только по критерию «слово можно убрать из предложения без существенной потери смысла». Этот критерий работает не всегда: с одной стороны, из предложения могут быть убраны без существенной потери смысла некоторые обстоятельства, но это не повод считать их вводными словами (вводными сочетаниями); с другой стороны, некоторые вводные слова и сочетания в значительной степени формируют смысл предложения, так что убрать их затруднительно. Специфика вводных слов состоит в их семантике: они вносят в предложение субъективные значения, исходящие от автора или (реже) от другого лица. Так, слово возможно указывает на степень достоверности сообщения, факта; с его помощью автор сигнализирует, что высказывает предположение, а не утверждает что-либо уверенно. Это одно из типичных значений вводных слов и сочетаний. Список таких значений приведен в справочниках, например в примечании к параграфу 91 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина.
Оба варианта возможны.
Оба варианта корректны. Второй - более разговорный.
Мекка – существительное женского рода. Так что ошибки нет.
Запятая ставится.
Оба варианта верны.
Это устойчивое выражение.
