Running /etc/rc.d/init.d/sendmail restart tends to leave the sendmail daemon down. The redhat rc daemon() function checks to see if any processes with the daemon's name exist, and if so, will not start the daemon. For sendmail, this is a bad idea, as there are often queue jobs still running when the main daemon exits. More generally, this behavior of daemon() is questionable. There are probably other daemons out there that behave like this.
This problem still exists in 6.2 "sendmail start" should probably wait a bit (15 sec) for queues to complete, and then start blowing them away.
*** This bug has been marked as a duplicate of 20696 ***