Такое сочетание возможно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прилагательные с подчинительным отношением основ и с суффиксом в первой части пишутся по словарю: частноправовой, железнодорожный, но естественно-научный, публично-правовой. Полное правило см. здесь. Спасибо за найденную неточность в ответе!

Можем предположить, что упругодеформационный - производное от подчинительного сочетания "упругая деформация" (ср.: упругая пластичность). В то же время упруго-вязский - от сочинительного сочетания "упругий и вязкий", "вязкий, но упругий". В этом различие.

Мягкий знак пишется в неопределенной форме глагола (что делать? изменяться). Мягкий знак не пишется в формах 3-го лица единственного и множественного числа (что делает? изменяется; что делают? изменяются). Это правило можно найти в любом учебнике и справочнике по правописанию.