I've gotten this notice quite often lately when I send email "Delivery Status Delayed", "Mail to the following recipient________ has been delayed"

What does this notice mean and why am I getting it more and more? I send an email and 24 hours later I get a notice that says it hasn't even been deliverd.

When you send mail, your client, a mail user agent (MUA) connects to some mail transport agent (MTA). The MUA could be IE, Thunderbird, etc. The MTA could be sendmail, MS Exchange, or something else.

It is the responsibility of the MTA to actually route your mail to some MTA which gets the mail to the recipient (this is determined by the domain record). If for some reason your MTA is unable to contact the recipient's MTA, the mail message is queued and retried. The parameters are adjustable, but in general your MTA will not inform you immediately that it has queued your message; it will inform you after a few hours that your message is in the mail queue. This queue is processed regularly (at least once per hour) and your message sits in the queue until delivered, or until it is tossed which is usually about four days (another adjustable parameter).

If you get these messages, it means one of three things. Either the recipient's MTA is flaky or not continually net-connected, or yours is. Or your MTA is attempting to contact the incorrect remote MTA due to incorrect or polluted DNS records.