mail not queued when server down. email was rejected

You could use a Frontend or bridgehead Exchange server to receive and queue your mail.
The other option would be a hosted company like Postini

Mail should have queued, unless the sender has a very low time out period. Most servers will retry for up to 48 hours.
However what you haven't said is what the NDR said, how your email flows and what you mean by "down". There are some scenarios where the email will reject immediately, but in most cases the most the sender should get is a delay message.

Simon.

Well in this case, the server was not connected to the internet due to an incorrect IP setting on the router, and it was a few hours before we got it straightened out.
But we were looking for a solution where it could handle even the case of a power outage and the server could be off (not powered on) for over a day if it happened on a weekend... for example.

Oh and also, I don't have the exact NDR, but it said something like "no such domain exists."  That was why we were concerned for a client to see that.  If it just said there would be a delay, we might be OK with that, but this stated a delivery failure.

The solution I proposed does queue your emails on their servers in case of any outage where your Excange Server is unreachable.

-saige-

Without the exact NDR it is impossible to know what the cause of the problem is.
You do not have to use a third party service to maintain email services, and a server dropping off the internet for a few hours should not cause email to fail, unless there is something about the setup that you haven't stated or don't know about.
For example, the server was also the PUBLIC DNS server for your domain, so external senders could not query your DNS records for the MX records. That would generate an instant failure of email if the server wasn't available, but is easily corrected by using different DNS servers.
Furthermore, if that was the problem (theoretically) then it would still occur even if you used a third party service for routing your email through.

A server being unavailable for a few hours should not result in the loss of any email. A few delays maybe, but complete loss, no. Third party services are not required to maintain email services. I have built 100s of serves and not one of them uses a third party service for full email service.

Simon.

Simon,

In most cases I would agree with you, however, with regards to maintaining email services, in my experience companies can be without mail services for days sometimes because of an uncontrollable event (major server outage caused by hardware failure, power outage, natural disaster, etc. etc.) and sometime emails services are down for controllable events (planned outages due to server modifications, physically moving from one location to another, changing ISPs, etc. etc.).  Now usually this does not happen for larger corporations who can have multiple Exchange Servers with fail-over internet connections, but for Small Business these situations are a reality.

What the poster is really after is not emails resent after delay (In this case, Simon is spot on, sending mail servers will queue emails internally for an allotted timeout period.  If the time out period is reached and the email has not been sent successfully, an NDR Report is generated and sent back to the sender.) but rather a solution that will allow his company to save face to their clients in cases of a critical outage where their server is offline.  He does not seem so concerned with what was being sent back to his clients but rather that something was sent back to his clients other than his reply.

As such he simply wants to use something to queue emails until such a time as email services are restored.

-saige-

I don't disagree.
However, as the server isn't behaving correctly, without knowing the core of the problem using another service may not help. If the problem is DNS as per my example, you can set the MX records to be anything you like, if the DNS server is down then email is not going to be delivered, whether that is delivery to an ISP's server, Postini, or the own server.

The core functionality isn't working correctly. Using another service is like deciding that driving a BMW off a cliff isn't a good idea, so I will use a Mercedes instead. Doesn't resolve the underlying problem of why am I driving off a cliff.

Simon.