What happens when a mail server goes down
Solution 1:
The SMTP protocol is very resilient in design. Most modern MTAs will attempt to resend a message every 4 hours for up to 5 days though this is configurable by the particular systems admin there is usually very little need to change from this.
The only server you would need to be concerned about would be the initial server you're connecting to in order to send the message. So long as this server accepts the message into it's queue it will continue to be processed until it can no longer be sent and then a undeliverable message will be sent back notifying you. Once it has been accepted by the initial MTA you're concerns about it's delivery should be negated regarding maintenance and restarts. Also given that many larger mail providers run clusters of mail servers it's likely that the maintenance and restarting of any one will affect mail transmission.
Solution 2:
It be returned as undeliverable. Depending on the senders server configuration, it may retry several times before finally giving up. We use Network Solutions as our MX. Te likely hood of them having an issue is much lower than us. Not to mention, we can do maintenance anytime we like, as all the mail is then captured from the NetSol servers when we are back online, and our senders don't get any bounces.
In addition, running a mail server inside a VM is harmless, as long as it has the resources it needs to function.
Solution 3:
Nothing wrong with using a VM to run a mail server, though if you're using exchange, you'll need to be careful with resources.
Dan's right. Most external mailservers will try to re-deliver several times before they give up.
I tend to set up a mail relay upstream of my actual mailserver, so I don't have to put my actual server out there on teh interwebs. You can set up a relatively foolproof sendmail server that only does relaying for practically nothing, and it removes a lot of stress when you have users that are really attached to their email. Even if your local server goes down often, you can setup your relay to keep the incoming mail until delivered.