I use sendmail and never have this problem... because it's configured properly ( well mostly ).
What you want to do is make sure sendmail is in queue mode, so it queues the messages first, then when it runs the queue it delivers them ( or attempts to).
Here's some code for the sendmail.mc file, the first one puts it in queue mode, the last few make sure no dns lookup is done on the initial pass from LMP to sendmail:
define(`confDELIVERY_MODE', `q')
define(`confDONT_PROBE_INTERFACES', `true')
define(`confDIRECT_SUBMISSION_MODIFIERS', `C')
define(`confBIND_OPTS', `-DNSRCH -DEFNAMES')
FEATURE(`nocanonify', `canonify_hosts')
Let me know if that helps. If you are familiar with sendmail this will make sense, if not it will be crazy... rebuild your .cf file and restart sendmail.