I had a sort of same problem with my mail in the beginning, this is only on setups with centos 5.3 i think
If you install postfix with 'yum install postfix' it installs postfix without mysql and you need the with mysql option. This is a problem of the default repo's of centOS.
You need thisone:
Installed Packages
Name : postfix
Arch : i386
Epoch : 2
Version : 2.3.3
Release : 2.el5.centos.
mysql_pgsql
Size : 8.3 M
Repo : installed
Summary : Postfix Mail Transport Agent
URL :
http://www.postfix.org
License : IBM Public License
Description: Postfix is a Mail Transport Agent (MTA), supporting LDAP, SMTP AUTH
If this package is also not in the rpmforge repo than you have to download the .rpm from a rpm search site and install it