"If i ran the command myself, as user nagios or any other, it works fine and the mail arrives."
This would certainly appear to rule out a sendmail configuration problem, unless I'm missing something? I suddenly find myself experiencing a similar problem - the nagios alerts are not being delivered, but I can cut and paste the command from the "host delivery notification timed out" error in the nagios.log, and it will deliver the notice with no problems.
When the notice was queued by nagios,my maillog indicates a message connection was initiated but there was no message body or recipients:
"from=nagios, size=0, class=0, nrcpts=0, relay=nagios@localhost"
When I paste the failed command from the nagios.log at the command line, the maillog looks good:
"from=nagios, size=436, class=0, nrcpts=1, msgid=<"SENDMAIL ID HERE">, relay=nagios@localhost"
And a few seconds later, the message is in the appropriate inbox. I get the exact same result regardless of the destination address (local system, corporate notes server, gmail address) or mailer (/bin/mail, /bin/mailx) - it always results in a timeout in the nagios.log, and it always works from the commandline. This host also delivers localmail from other applications, relays external notices for other domains, and delivers external notices from various cron jobs.
Anyone have any thoughts that don't involve dismissing this offhand as a "sendmail problem"?