Глагольное управление: прозвать кого-что кем-чем. В названии «Врата ада» нет оснований для написания второго слова с прописной буквы. Правильно:  Неудивительно, что местные жители прозвали это место «Дверью в преисподнюю» и «Вратами ада».

Наречие вновь имеет два значения (смБольшой универсальный словарь русского языка):

ВНОВЬ, нареч.

● 1.0. Ещё раз. Син. опять употр. чаще, снова употр. чаще, ещё¹. Увидеться в. Вчера он в. опоздал. Аня в. и в. убеждала нас не продавать дачу. ● 2.0. Впервые, только что. В. созданная организация. Все квартиры во в. строящемся доме уже проданы. ◒ Единожды солгавши, кто вновь тебе поверит – см. поверить. || Морф. в=новь. Дер. От прил. новый (См.).

Так что выражение вновь созданный может означать и "впервые созданный", и "еще раз созданный". 

Способ словообразования устанавливается на основе анализа словообразовательной пары путем сравнения производной и производящей основ. При этом учитывается значение словообразовательных средств и регулярность их использования при образовании слов по определенной словообразовательной модели.

Вся словообразовательная цепочка, приводящая к образованию производного слова, учитывается при морфемном анализе, а не при установлении способа словообразования.

Глагол истолковать образован от глагола толковать приставочным способом. Приставка из-/ис- вносит значение ‘совершить (довести до результата) действие, названное производящим глаголом’, ср.: мерить → измерить, лечить → излечить, жарить → изжарить, уродовать → изуродовать, купать → искупать и т. п.

Большой толковый словарь

Слово богорадничать не зафиксировано в толковых и этимологических словарях русского языка.

Синонимический ряд богорадить, богарадствовать (тамб.), богоугодствовать, богарадничать, проживать Христа ради включен В. И. Далем в «Толковый словарь живого великорусского языка». Региональная диалектная помета (тамб.) есть только у слова богарадствовать, поэтому мы не располагаем сведениями о региональной принадлежности этих слов. Отсутствие лексикографической системности и последовательности при сборе и подаче материала является отличительной чертой словаря Даля, созданного языковедом-любителем.

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

Да, в современном русском языке в глаголе избегать 'сторониться чего-либо, уклоняться от чего-либо' выделяется корень избег-, а в глаголе избегать 'бегая, побывать во многих местах' – корень -бег-. Разумеется, исторически в слове избегать тоже выделяется корень -бег- и приставка из-, оно родственно глаголу бежать 'сторониться'. Но в современном языке приставка в этом глаголе уже не выделяется.

Глаголы "присутствовать", "находиться" и "числиться" различаются в первую очередь смысловыми оттенками, в конечном счете выбирать Вам исходя из требуемого содержания. Если в Вашем случае нельзя избежать использования слов "в подведомственности", то следует просто руководствоваться толковым словарем. Обратите внимание на синонимические ряды (приводим синонимы только для актуальных значений): присутствовать = иметься, наличествовать; находиться = располагаться, быть, пребывать; числиться = "иметься у кого-либо или быть в каком-либо состоянии согласно записи, документу и т. п.". Просим также обратить внимание на то, что глагол "присутствовать" в указанном значении вполне корректно сочетается с неодушевленными существительными.

Кстати, сочетание "подразделение организации находится на территории, подведомственной определенному налоговому органу" кажется нам более удачным. Может быть, так и оставить?

Если поискать, такие слова найдутся) Например, буквосочетание гя может встретиться в именах собственных (Плунгян — фамилия ученого, академика РАН, главного научного сотрудника Института русского языка им. В. В. Виноградова РАН). Буквосочетание гя встречается в формах деепричастий глаголов на -жечь (*зажгя, *разожгя), ненормативных, но используемых, например, в художественных текстах — в стилистических целях, для передачи особенностей речи персонажей и др.: И далее вижу я — боярский сын, и ремесленник, и крестьянин берут кистень и, зажгя дворы свои, уходят в леса свирепства своего ради (А. Н. Толстой, Петр Первый); Пробовали даже выкуривать обитателей норы, разожгя костер (В. Солоухин, Капля росы). Наконец, всегда есть возможность образования окказиональных слов, содержащих данное буквосочетание.

Обычно непроизносимое s в англоязычных именах собственных при транскрипции опускается. Например: Long Island — Лонг-Айленд. При переводах английской литературы на русский язык давно существует традиция написания Гровнор: «Тетушка, — продолжала она, — собирается завтра побывать в той части города, и я воспользуюсь случаем, чтобы нанести визит на Гровнор-стрит» (Джейн Остин. Гордость и предубеждение. Пер. И. С. Маршака, 1967) и т. п.

Допустимы оба варианта: Я всегда хожу накрашенная и Я всегда хожу накрашенной. 
См. ходить в «Большом универсальном словаре русского языка»:

13.0. Находиться, пребывать в каком-л. состоянии, положении и т. п. Син. бегать.

Ходить в каком-л. виде (в каком-л. состоянии, в каком-л. настроении …). Кто-л. ходит раздетым / раздетый (голым / голый, босым / босой, голодным / голодный, весёлым / весёлый, грустным / грустный, пьяным / пьяный, довольным / довольный, подавленным / подавленный, беременной / беременная, убитый горем …)

В предложениях Я хожу ненакрашенная и Я хожу ненакрашенной Вы верно написали не с причастием. Если в предложении нет противопоставления (Пришла не накрашенная, а умытая) и у причастия нет зависимых слов (Из-за не накрашенной до конца актрисы съёмки отложили), не с причастием пишется слитно.