I recently ran into a problem where one of my CentOS machines was taking a very long time (a couple of minutes) to start the sendmail and sm-client servies at boot time. I found the fix was quite simple.
The problem in my case was resolved by making sure the hostname was correctly added to the loopback entry at the top of /etc/hosts.
127.0.0.1 thehost localhost.localdomain localhost