JMS spec specifies FIFO order of messages if they are sent by one publisher and consumed by one consumer. order of messages between different publisher is not garanteed (There is no easy way to know which message got sent first between publishers)
Actually, I've been seeing a problem with JMS Queues with one producer and one consumer.
On Producer: Message A is put onto the queue before Message B.
On Consumer: Message B is processed before Message A.
I only have one MessageListener for the session connected to that Queue.
BTW, I noticed that both messages get the same timestamp on the producer side. I don't know if that effects the ordering but it darn well shouldn't, especially with a queue.