I have one centos 4.0 server which /var/log/messages was always empty (0 bytes). I wonder what has been blocking the syslog to write the log.
Firstly, I'd suggest updating to 4.5.
Secondly, is /tmp mounted with noexec option?
forgot to add, check /var/log/messages.* for current syslog messages