Евгений Николаев, Ваше сообщение прям спасло. Оказалось, что перевод агентов на cron был сделан для пользователя root, из-за этого в кеше некоторые каталоги создавались с рутовыми правами. Соответственно, у пользователя www-data (под которым работает apache) не было прав на перезапись некоторых файлов, которые как раз были нужны для отправки почты. Убрав cron-задание от пользователя root и добавив его пользователю www-data, проблема решилась - почта стала улетать без проблем.