What availability is needed for an E-Mail server to not lose messages?

The place to look for an official answer to this question is RFC 5321. Here is what RFC 5321 has to say:

Retries continue until the message is transmitted or the sender gives up; the give-up time generally needs to be at least 4-5 days. It MAY be appropriate to set a shorter maximum number of retries for non- delivery notifications and equivalent error messages than for standard messages. The parameters to the retry algorithm MUST be configurable.

So, if your server stays down for even three days, you shouldn't expect any mails to be lost, but they will of course get delayed.

A couple of advantages to having two MXs on different networks are:

• You avoid most emails getting delayed when one of the two is down.
• You have less risk of emails unable to be delivered when connectivity problems unbeknownst to you prevent a single sending server from reaching one of the networks hosting an MX of yours.

When mail servers have to deliver emails to you(r mail server), they must maintain a queue for when your mail server is offline. From Wikipedia:

Fully capable SMTP servers maintain queues of messages for retrying message transmissions that resulted in transient failures.

The Postfix documentation also provides some more information on this.

Thus, as long as your mail server doesn't stay down for too long, you wont lose any emails. That being said, a redundant setup is of course better so you receive the emails almost instantaneously and you can keep sending out emails as well.

Edit: Sending out emails can be done by a completely different server. Your question was only for receiving email so that server going down does not necessarily impact your capability to send emails.