mail arriving out of order?

If your users complain about mail arriving out of order you can tell them the story below. But if they're complaining that this happens a lot, it's probably a symptom of your MTA being overloaded.

The mail protocol makes no guarantee that your messages will arrive in order.

If the mail server for foo.com tries to relay message-0 sent at 2:00 to mta0.domain.tld and mta0 doesn't have the resources it can and will refuse the SMTP connection. It's also possible that foo.com will then put message-0 back in its queue to not be resent for as long as root@foo.com sees fit to configure it. Let's assume this value is 1 hour. foo.com could then try to send message-1 (this not not message-0 which is still in the queue) at 2:05. When it tries to get it's SMTP connection this time mta0 has resources at that moment and accepts the message for delivery. Then at 3:00 foo.com tries to make another connection for message-0 to mta0 which again has resources and accepts the message. So, in the end message-0 sent at 2:00 arrives at 3:00 and message-1 sent at 2:05 arrives at 2:05. All of this is perfectly legal.