почта

Провайдер ничего не должен, кроме как дать тебе нормальный IP и снять на тебя файрволы (каких скорее всего и не стоит), а вот ты должен сходить на курсы или почитать умные книжки про DNS, SMTP и всякие sendmail/procmail/exim/postfix/qmail. Ну или нанять специалиста (предпочтительней).

P.S.: специалист - это не товй знакомый h4X0r, а тот, кто сможет сделать работу быстро и качественно. И это не будет "нахаляву" - ибо бесплатного никто не обещал.

если твоя личная почта, то просто купи хостинг с доменом у любого прова.
как вариант сгодится и для малого офиса.
например masterhost.ru, nthost.ru