Сергей

Попробуй так отправить:

$message = 'test mail from server';
mail("to_email@mail.ru", "the subject", $message,
"From: email@domain.ru\r\n"
."Reply-To: mail@domain.ru\r\n"
."X-Mailer: PHP/" . phpversion());

У mail.ru есть еще проверка правильности домена. domain.ru должен отдавать ip твоего сервера.

Если не поможет - проверь ptr и логи

Пускать сайты под разными пользователями, ограничить права доступа, отключить shell.

cat /var/log/yum.log
Может что то по мимо php обновилось? Если в php mail(); работает то дело врятли в нем.
echo "test" | sendmail -v -f ящик_на_сервере почта_куда_отправить - что говорит?
проверь еще relayhost в main.cf

yum groupinstall "Development Tools"
Покажите еще вывод df, dmesg