Вы привели отличный пример того, что вводное слово не определяется только по критерию «слово можно убрать из предложения без существенной потери смысла». Этот критерий работает не всегда: с одной стороны, из предложения могут быть убраны без существенной потери смысла некоторые обстоятельства, но это не повод считать их вводными словами (вводными сочетаниями); с другой стороны, некоторые вводные слова и сочетания в значительной степени формируют смысл предложения, так что убрать их затруднительно. Специфика вводных слов состоит в их семантике: они вносят в предложение субъективные значения, исходящие от автора или (реже) от другого лица. Так, слово возможно указывает на степень достоверности сообщения, факта; с его помощью автор сигнализирует, что высказывает предположение, а не утверждает что-либо уверенно. Это одно из типичных значений вводных слов и сочетаний. Список таких значений приведен в справочниках, например в примечании к параграфу 91 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина.
Однозначный ответ на Ваш вопрос дать сложно. Местоимения 3-го лица он, она корректно употреблять, когда речь идет о лице, не участвующем в разговоре, отсутствующем (это не является признаком неуважения к человеку). Но не тогда, когда человек принимает участие в разговоре. Вот что написано в «Словаре русского речевого этикета» А. Г. Балакая: Употребление местоимения он, она по отношению к собеседникам, без предварительного называния их по имени (имени-отчеству) считается невежливым: говорящий как бы исключает собеседника из общения, демонстрируя тем самым неуважительное к нему отношение.
Так что вопрос заключается вот в чем: можно ли считать Вашу коллегу отсутствующей при разговоре? С одной стороны – да, когда Вы просили коллегу передать ей что-то, то этот разговор шел только между вами двумя, а она находилась в другой комнате и к данному диалогу отношения не имела. А следовательно, формально правила этикета Вы не нарушили. С другой стороны, слыша Ваш голос в телефонной трубке, она «виртуально» все-таки присутствовала при разговоре, поэтому формально у нее был повод обидеться на Вас.
Согласно правилу отрицание не пишется слитно, если после не, имеющего отрицательный смысл, следует часть слова, отдельно (без не) в качестве самостоятельного слова не существующая: нездоровиться, несдобровать и т. п. С (не)поздоровиться как будто бы такая же ситуация, однако у правила есть примечание: по традиции пишутся раздельно не поздоровиться, не преминуть, не обессудь(те), не обинуясь. Возможно, это связано с тем, что глагол поздоровиться все-таки может употребляться самостоятельно, хотя и в редких случаях, например: Тогда же посмотрю, поздоровится ли русской литературе [А. В. Дружинин. Письма иногороднего подписчика о русской журналистике (1849)]; ...«аналогия» с «загнивающим» капитализмом была бы полная, но от этой «аналогии» вряд ли поздоровится «социалистическому накоплению» [Н. И. Бухарин. Новое откровение о советской экономике или как можно погубить рабоче-крестьянский блок (1924)]; Рассказывал, как шел, голодал, служил банщиком, многое путал, так что если бы он рассказал так следователю, который допрашивает партизан, перешедших фронт, вряд ли бы Петру Лазаревичу поздоровилось [Вс. В. Иванов. Дневники (1940-1948)] и др.
Первая часть предложения не является устойчивым выражением, это придаточная часть. Отделить ее можно запятой, но в данном случае возможно и тире.
С большой буквы нужно писать официальные названия министерств, отечественных и зарубежных (то есть писать так, как эти названия оформляются в документах). А вот сочетания типа "минздрав США" можно написать со строчной.
Не обособляются определения, стоящие после определительных местоимений (в том числе весь) и образующие с ними единую группу (ударение падает на определение). Запятая после все не требуется.
Что касается второго вопроса, то не вполне ясен смысл слов по легенде учений. Если они указывают на источник сообщения, то могут быть вводными и обособляться.
В данном случае для вставной конструкции лучше использовать скобки: С моей стороны (я очень надеюсь, что ничего не случится) всё остаётся прежним: 23-го прибываю, 27-го отправляюсь обратно.
Запятая требуется только перед союзом то бишь: Он находится лицом к девушке и начинает идти назад, то бишь ведя ее вперед.
Наличие союза что не влияет на знаки препинания при слове безусловно. Подробнее о пунктуации в этом случае см. в "Справочнике по пунктуации". Верно: Я увидел его с иной стороны, что, безусловно, меня поразило.
Экспертный совет Тотального диктанта в 2010 году принимал как допустимые оба варианта (и с запятой, и без нее) и комментировал эту пунктограмму так: «Все что угодно – запятую можно ставить и не ставить. Формально и исторически что угодно – это придаточное предложение (поэтому можно поставить запятую), но оно уже превратилось в устойчивое выражение (=разное, непредсказуемое, поэтому запятую можно не ставить). Национальный корпус русского языка показывает разные варианты пунктуации при этом обороте. Во всех текстах Стругацких из Национального корпуса запятая стоит. Но в печатных изданиях Стругацких встретился пример без запятой».
Мекка – существительное женского рода. Так что ошибки нет.