Дмитрий Просто

Администрирование почтовых серверов, готовые частные и корпоративные почтовые серверы: mailout.ru
Или можно изучить компании из этого списка: mailout.ru/hostingi-pochty

На этапе удаления домена из Яндекс.Коннект.

Попробуйте вернуть домен в прежний аккаунт Яндекс.Коннект. Затем написать поддержке Яндекс.Коннект с описанием ситуации и вопросом, что можно сделать.

Если для рассылок используются не шаблоны, предлагаемые сервисом, а самостоятельно сверстанные письма, и все равно добавляется рекламная подпись, то ее добавляет сервер, и убрать ее в этом случае нельзя.
Только используя тарифный план данного сервиса без рекламы. Или собственный почтовый сервер.

Настройка почты на любом платном хостинге не легче, чем на сервисах Яндекс, Майл, Гугл.
Оптимальным вариантом, думаю, для Вашей задачи будет Mail.ru. Настроить надо один раз. Других временных затрат сервис не требует. Если уже есть зарегистрированный домен, процедура настройки занимает не более суток, с учетом переноса домена.
Если нужна помощь , обращайтесь.

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

На хостингах с фильтрацией входящей почты на спам действительно дело обстоит хуже, чем на сервисах Mail.ru, Yandex.ru. С исходящей почтой теоретически могут быть так же неприятности, зависит все от хостера и внимания, которое он уделяет поддержке сервиса почты.

Если требуются автоматические отправки с сайта какой-либо информации (событийные письма, заказы и т.п.) большой шанс получить проблему при использовании корп. почты данных сервисов.

Просто для корпоративной переписки Mail.ru, Yandex.ru вполне подойдут. Для отправки с сайта лучше корпоративную почту на своем сервере.