В XIX в. многие прилагательные имели вариантные формы – с основой на твердую и мягкую согласную и образовывали падежные формы как по твердой, так и по мягкой разновидности. Сюда относятся: бескрайний, внутренний, давний, дальний, долголетний, ежегодный, загородный, иногородний, искренний, исконный, малолетний, многолетний, односторонний, поздний, тутошный (прост.). Следующие употребления этих слов отличны от современного: Душевных мук волшебный исцелитель, Мой друг Морфей, мой давный утешитель (Пушк.); Для берегов отчизны дальной Ты покидала край чужой (Пушк.); В предместиях дальных, Где, как черные змеи, летят Клубы дыма из труб колоссальных (Некр.); Иногородные могут адресоваться в Газетную экспедицию (Пушк.).

В современном языке прил. внутренний, давний дальний, долголетний, иногородний, искренний, многолетний, односторонний, поздний образуют все падежные формы по мягкой разновидности, прил. ежегодный, загородный, исконный, пригородный – по твердой разновидности. Употребление, не отвечающее данному правилу, является устарелым: Дальная знакомая приютила моих детишек (журн.); Укротить Россию и потом ограбить ее, как до войны грабили Турцию, Китай, как собираются ограбить Германию, – вот искренное желание империалистов (Горьк.). В образовании падежных форм прил. бескрайний, междугородний и выспренний (книжн.) допускаются колебания, причем преобладают формы с основами на мягкую согласную: Дивизия, наступая, углубилась в бескрайние леса (Казакевич); Поехал на междугороднюю станцию (Симон.); Восхвалял театр, употребляя неимоверное количество иностранных слов и выспренних выражений (Н. Вирта). Сравним: Лес на горизонте утопал в бескрайной воде (Г. Березко); Бекетов жил и вырос в бескрайных песках Туркмении (Гайдар); Снимает трубку, звонит на нашу междугородную (Полев.); Никаких выспренных требований к нему не предъявишь (Фед.).

(Источник: Русская грамматика, 1980).

Варианты, о которых Вы пишете, — яркая черта старомосковского произношения. В речи коренной московской интеллигенции XIX — первой трети XX века согласный перед мягким согласным тоже был мягким. Наиболее последовательно это реализовывалось в сочетаниях зубных с мягкими зубными: [c']тена, [c']нег и т. д. В течение XX века это произношение постепенно уходило из живой речи, но сохранялось, например, в речи актеров, дикторов. Сейчас такие варианты в одних случаях уступили свои позиции новым нормам, но еще не ушли из языка совсем, они даются в словарях как допустимые, но устаревающие или устарелые: во[с]питатель u допуст. устарелое во[с’]питатель; [с]мех и допуст. устарелое [с’]мех. В других случаях они еще рекомендуются в качестве образцового литературного произношения: [с’]нег и допуст. младш. [c]нег.

Дело в том, что вы приводите ОРФОГРАФИЧЕСКОЕ правило (правило правописания), а спрашиваете - о СЛОВООБРАЗОВАТЕЛЬНЫХ законах. Это разные вещи. Слова с первой частью на -О (крово-, песно-, зверо-, басно-) по преимуществу имеют книжный характер и восходят к церковнославянизмам.

Перенос деревь-ев правилен. Буквы ъ и ь не разрешается отделять от предшествующей согласной, т. е. неправильным был бы перенос дерев-ьев. А перенос деревь-ев полностью соответствует правилам переноса. См.: Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006. § 213.

Мягкий знак во втором случае не нужен, никакое правило под это подвести нельзя. Сообщения (что делают?) удаляются – Сообщения будут (что делать?) удаляться.

В этих словах нужно писать О, поскольку согласный, предшествующий соединительной гласной, твердый.

Правильно написание без мягкого знака.

Словообразовательный разбор

Схема разбора:

1)    Поставить исследуемое слово в начальную форму.

2)    К исследуемому слову подобрать производящее.

3)    Объяснить значение производного слова через значение производящего слова (слов).

4)    Выделить производящую и производную основы.

5)    В производном слове выделить средство словообразования.

6)    Указать способ словообразования и процессы, сопутствующие словообразованию.

Разбор слова поверье:

1)    поверье — начальная форма существительного;

2)    поверье ← поверить;

3)    поверье: ‘предание, основанное на суеверных представлениях, приметах, необычных явлениях чего-либо, в которое кто-либо поверил’;

4)     повери- — производящая основа, повер[j] — производная основа.

5)    средство словообразования — суффикс -j-, который на письме передается с помощью разделительного мягкого знака: повер[j-е];

Такое же словообразовательное средство с тем же значением используется при образовании других отглагольных существительных, например: бесчести-ть → бесчест[j-е] (бесчестье).

6)    способ словообразования — суффиксальный, при словообразовании происходит усечение производящей глагольной основы: повери-. 

Если необходимо разобрать слово по составу (морфемный разбор), то словообразовательный разбор дополняют:

1)    анализом всех словоизменительных морфем слова.

2)    анализом всех словообразовательных морфем в слове.

Для слова поверье при морфемном анализе нужно выделить:

1)    окончание -е, которое является окончанием им. падежа (или винит. падежа, если в такой форме слово стояло в предложении; формы именит. и винит. падежей у этого слова совпадают), ед. числа, ср. рода.

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

Полный разбор по составу: по-вер-j-е