Sendmail delaying mails for 45 mins

Hi,

I'm trying to send out mails from my server using mailx, however everytime I send one, it appears to be held in the /var/spool/mqueue for 44 mins before being sent.

I'm quite new to sendmail, so don't really know where to start with this /var/log/syslog displays the following:

Dec 16 17:00:59 client01 sendmail[24805]: [ID 702911 mail.info] STARTTLS=client, relay=mailhost, version=TLSv1/SSLv3, verify=FAIL, cipher=DHE-RSA-AES256-SHA, bits=256/256
Dec 16 17:00:59 client01 sendmail[24805]: [ID 801593 mail.info] rBGGG2MP024799: to=<xplus@mycompany.com>, delay=00:44:57, xdelay=00:44:57, mailer=esmtp, pri=124456, relay=mailhost [10.58.1.56], dsn=2.0.0, stat=Sent (Ok: queued as C47E042434F)
Dec 16 17:01:00 client01 sendmail[24898]: [ID 702911 mail.info] STARTTLS=client, relay=mailhost, version=TLSv1/SSLv3, verify=FAIL, cipher=DHE-RSA-AES256-SHA, bits=256/256
Dec 16 17:01:00 client01 sendmail[24898]: [ID 801593 mail.info] rBGGG2H7024896: to=<xplus@mycompany.com>, delay=00:44:58, xdelay=00:44:57, mailer=esmtp, pri=123116, relay=mailhost [10.58.1.56], dsn=2.0.0, stat=Sent (Ok: queued as 4D6E542434F)
Dec 16 17:01:00 client01 sendmail[24900]: [ID 702911 mail.info] STARTTLS=client, relay=mailhost, version=TLSv1/SSLv3, verify=FAIL, cipher=DHE-RSA-AES256-SHA, bits=256/256
Dec 16 17:01:00 client01 sendmail[24900]: [ID 801593 mail.info] rBGGG2H9024896: to=<xplus@mycompany.com>, delay=00:44:57, xdelay=00:44:57, mailer=esmtp, pri=124457, relay=mailhost [10.58.1.56], dsn=2.0.0, stat=Sent (Ok: queued as 67EE8424351)

Any ideas on where to start? I've tried looking at sendmail.cf for any default queue options, but it might as well be written in klingon, I can't make head nor tail of the output!

One of the startup options specifies how frequently queued messages are processed. See manpage for -q [Time] option. Do a COLUMS 132 ps -aef | grep sendmail to check for the start up options if any running on the current process. You can temporarily stop the current sendmail and do something like

sendmail -bd -q 

(this would process all queued mail immediately and push process in background).

sendmail -bd -q10m

(this would process queued mail every 10 minutes

You can also telnet to sendmail ports and test mail server.
(google for how to do that)

a ps -ef returns the following:

# ps -aef | grep sendmail
   smmsp   608     1   0   Nov 24 ?           0:18 /usr/lib/sendmail -Ac -q15m
    root   610     1   0   Nov 24 ?           3:31 /usr/lib/sendmail -bl -q15m

I do not believe the above is anything out of the ordinary.

Does the syslog output in my first post indicate that the mail relay server is accepting the mail?

I think the STARTTLS messages do not mean a delay.
The mail client is configured to use TLS for outgoing mails.
You should rather look for stat= lines that are not Sent

grep "stat=" /var/log/syslog | grep -v "stat=Sent"

I think it could be a slow relay so the path the mail is taking could be an issue. The "relay=" value above in your log entries. So, from the process list you show it is set to 15 minutes queue processing time I think. Try sending mail from the host to itself. Then try sending mail withing your domian, then outside your domain. You can stop and start sendmail to send the main immediately so you don't have to wait for the queue time. I sometimes will telnet to the smtp port of a mail server to see how it responds (if security allows it). So you could test your relay servers.