IMHO it shouldn't be guaranteed, and that order should be represented in the packets (such as with a sequence identifier in the packet) can be used to delay processing for sequences that require in-order delivery.
Instead of making up new mechanisms like sequence numbers, why not just have the server add a timestamp to every message via the jabber:x:delay namespace?
—Jens
