I've noticed this problem while flushing selected messages in the Sendmail module. I'm not sure if it also happens in the Postfix and Qmail modules, and I'm also not sure if it happens when flushing the entire queue (vs. only selected messages).
When displaying a mail queue, the order is preserved, based on the mail queue ID (i.e. delivery order) by default. However, when flushing these messages, they appear to be processed in a different, possibly random, order. They should be processed in the same order they appear in the mail queue display to preserve the original or selected delivery order when flushed.