1. Действительно, повторения двоеточий в одном предложении следует избегать, и если в предложении возникает необходимость в постановке двух двоеточий, то одно из них заменяют тире. Такая замена допустима правилами — см., например, примечание 2 к параграфу 129 справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина. Добавим, что в данном случае вполне возможно разделить одно предложение на два: Мария слышит, что её вопросы даже звучат глупо. Она прекрасно знает брата: тот никогда бы не опустился до лжи, если бы не крайние обстоятельства.

2. Тире здесь, как и в предыдущем примере, допустимо, но двоеточие предпочтительно. Кроме того, возможна постановка запятой, потому что слово ведь в таком контексте может рассматриваться не только как частица, но и как союз. Если оставлять тире, то перед ним нужно убрать запятую: в этом случае для ее постановки нет оснований.

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

Как Вы уже поняли, никаких реальных ограничений на то, чтобы главное слово было собственным наименованием в кавычках, не существует. Безусловно, бывает, что такое название как раз и служит приложением (кафе «Березка»), но из этого нельзя выводить никакого правила.

Когда имеется обособление, решать, конечно, проще: в обоих Ваших примерах обособленные компоненты и являются приложениями.
 

В теории сложного предложения не говорится прямо, но подразумевается по умолчанию, что это явление моносубъектной речи. Суть сложного предложения в том, что говорящий (один и тот же!) или вынужден, или предпочитает выразить свою мысль не одним, а двумя (или более) простыми предложениями, грамматически связанными между собой при помощи специальных средств связи (ср.: Маша была довольна приездом брата. — Маша была довольна тем, что приехал брат).

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

Исторический корень в словах вера, верить, доверить, безверие, безверный, доверенный, доверчивый, недоверчивый и других родственных — -вер-.

При морфемном анализе в словах доверчивый и недоверчивый тоже выделяется корень -вер- (см. «Словарь морфем русского языка» А. И. Кузнецовой и Т. Е. Ефремовой).

При синхроническом словообразовательном анализе слова верить и доверить не рассматриваются как однокоренные, так как их значения в современном языке считаются не связанными. Ср.:

Верить — 1. Не сомневаться в наступлении, неизбежности, торжестве чего-л. предстоящего и желаемого. 2. Не сомневаться в достоинствах кого-чего-л., в наличии у кого-чего-л. определённых положительных качеств.

Доверить — Испытывать доверие к кому-чему-л., быть уверенным в том, что действия, свойства и т. п. кого-чего-л. не принесут вреда, неприятностей и т. п.

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

Слово смотря в приведенном Вами предложении является предлогом, поэтому запятая после него не нужна. Ср.: Смотря по тому, насколько дорогим будет размещение объявления.

Для выделения той части текста, которая является текстовым примером (как предложение Смотря насколько дорогим будет размещение объявления в Вашем вопросе), могут использоваться разные выделительные средства, в том числе кавычки или курсив.

Конструкции ни что иное, как не существует. 

Конструкции не кто иной, как и не что иное, как, в которых кто и что могут стоять в косвенных падежах без предлогов и с предлогами (не кого иного, как; не чему иному, как; не у кого иного, как; не с чем иным, как и т. д.), следует отличать от конструкций, в которые входят местоимения никто и ничто (тоже в разных падежах без предлогов и с предлогами). Ср. попарно следующие примеры: 1) Это не кто иной, как его родной брат. — Никто иной, кроме его родного брата, не может этого знать. 2) Это не что иное, как самый наглый обман. — Ничто иное его не интересует. 3) Он встретился не с кем иным, как с президентом страны. — Ни с кем иным, кроме президента, он не согласен встречаться. 4) Он согласился не на что иное, как на руководство всей работой. — Ни на что иное, кроме руководящей должности, он не согласится. В каждой паре первое предложение утвердительное, второе — отрицательное. (Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006. § 78, п. 3 раздела «Орфография».)

А. А. Зализняк в примечании об именах собственных в «Грамматическом словаре русского языка» писал, что некоторые составные имена вошли в русский культурный фонд как целостные единицы, например: Тарас Бульба, Санчо Панса, Ходжа Насреддин, Леонардо да Винчи, Жюль Верн, Ян Гус. Среди них есть такие сочетания, в которых первый компонент в реальном грамотном узусе не склоняется (читать Жюль Верна, Марк Твена), склонение имен в подобных сочетаниях — пуристическая норма, соблюдаемая в изданиях. А. А. Зализняк к таким склоняемым формам дает помету офиц. В некоторых именных сочетаниях первый компонент никогда не склоняется, к ним относятся, например, имена персонажей Дон Кихот, Дон Карлос. Цельность, нечленимость этих сочетаний проявляется и в орфографии. Ср. написание и форму имени, относящегося к реальному историческому лицу и персонажу драмы Шиллера: За XIX век реликвия сменила нескольких хозяев и в 1895 году попала в руки дона Карлоса, графа Мадридского и легитимного претендента на французский трон и Роль Дон Карлоса создана, так сказать, по форме его таланта. 

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