Уточните что именно требуется: иметь почтовые ящики в своем домене или отправлять почту именно с сервера.
Во первом случае можно использовать любую из почт для домена, бесплатные biz.mail.ru, pdd.yandex.ru.
Во втором случае зависит от того, как именно хостер "не резрешает", например разрешена ли отправка писем через submission, если сервис в принципе не разрешает коннекты наружу - то ответ "никак". Если submission разрешен и объем почты небольшой - регистрируйте ящик как в п.1 и отправляйте с авторизацией.