Also... do this to make sure:
service iptables status
service ip6tables status
service iptables save
service iptables stop
chkconfig iptables off
service ip6tables save
service ip6tables stop
chkconfig ip6tables off
then do
cat /selinux/enforce
and see what it says...
you should not have to reboot for the iptables to be disabled completely... but for selinux you must... but... it seems like you have already done this several times... may be a blocked port 25 like phoenix suggests...
EDIT: and just to make sure... you edited /etc/selinux/config and set SELINUX=enforcing to SELINUX=disabled ...... not SELINUX=permissive .... right?

