У нас как обычно своя сеть отделена от интернета пограничным маршрутизатором. Поставили вовнутрь почтовый сервер, он нормально отсылал почту. Потом в целях безопасности закрыли на его IP адрес все порты кроме smtp, imap, pop2,pop3,587, 80 (это на пограничном маршрутизаторе). А письма все равно неходят. Если снова все открыть опять ходят. Может еще какие порты?