/var/log/maillog не работает???

Перезапускал их?

Спасибо! Перезапустил и заработоло! Еще вопрос: при отправке почты клиентом (The Bat 1.22) иногда происходит очень большой тайм-аут (до 60 сек.), а иногда отправляет моментом. В остальном почтовый сервер работает нормально. В чем может быть проблема? Может мозгов мало 32Мб???

Поставь ДНС и пропиши обратную зону для пользовательских компов, с которых отправляется почта.

Примечание: то что сказано мной выше - ответ на второй вопрос