Эти сочетания представляются аналогичными сочетаниям соотносительных или близких по значению слов типа ложки-вилки, овощи-фрукты. См. пункт 4 параграфа 118 в разделе «Орфография» полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина.

Вероятно, читатель видит здесь возможность использования только родительного падежа: упала на голову (кого?) девочки. Так написать можно, но и дательный падеж вполне возможен, дательным падежом управляет глагол: упала (кому?) девочке на голову. Поэтому ошибки в заголовке нет.

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

Однако раздельно пишется сочетание предлога по и прилагательного другому, например: вчера я обращался к вам по одному вопросу, а сегодня обращаюсь по другому.

Слова "к тому же" не обособляются, но могут начинать собой присоединительный оборот, требующий обособления. См.: 384">http://www.gramota.ru/spravka/punctum/58384

См. в «Справочнике по фразеологии».

1. Корректно слитное написание в первых двух случаях.

2. Возможны оба варианта.

3. Здесь тоже возможны варианты. «Грамматический словарь русского языка» А. А. Зализняка фиксирует Сочи как несклоняемое существительное мужского и среднего рода. А согласно словарю-справочнику «Географические названия» Е. А. Левашова Сочи — неизменяемое существительное множественного числа, но рассматривается также как вариант мужской род, единственное число.

Правильно без предлога: наиболее вероятно, что 29 мая.

Верно: О прохождении стажировки Ивановым.

Вы правы в том, что в приведенных примерах деепричастие учитывая употреблено некорректно. Во всех трех случаях лучше использовать условное придаточное: Если учесть, что… Но деепричастие при этом не перестает быть деепричастием. Предлог не может подчинять изъяснительное придаточное, на это способно только знаменательное слово с определенным значением.

Некорректность употребления деепричастия заключается в следующем. Действие, обозначаемое деепричастием, должно выполняться тем же субъектом, что и действие, обозначенное глаголом-сказуемым. Но сочетание не может учитывать (в первом примере), словообразование — тоже (второй пример), стратегия — тоже (третий пример). Именно несоблюдение этого правила вы ошибочно именуете «согласованием со сказуемым» (согласования в грамматическом смысле здесь нет).