Интернета достаточно, только смотрит ли ваш почтовый сервер в интернет? Например по умолчанию exim привязывается к локальному интерфейсу 127.0.0.1. Соответственно он никуда и не смотрит.
Также есть такия штука как iptables, которая может перекрывать порты для доступа туда-и-обратно. Проверить - iptables -L -n
Ну и собственно что за почтовый сервер устанавливаете? И как его диагностируете?
Ну и чтобы поднять почтовый сервер, нужно про него еще и интернету рассказать через DNS-записи MX и SPF как минимум...
