If you are using receiveNoWait() and calling it immediately after creating the receiver its possible that the messages are in transient. In MQ, a message is only returned if it is immediately available by the client (and it may take some period of time for the first message to be delivered to the client from the broker). We have an RFE to cause noWait to block if a message "would" be available however it is not implemented at this time (or planned for any current release)
If you aren't using receiveNoWait(), are you using multiple consumers ? MQ batches messages to a consumer based on the setting of the consumerFlowLimit setting on the destination. By default this is 1000. For example, if you send 1010 messages and started two receivers the first might have 1000 messages routed to it while the second would get only 10. (its possible that they may be more evenly divided but this is the worst case). If you think you are running into this problem, you should decrease the consumerFlowControlLimit to 1 to see if that helps the problem. (you can later tune this variable based on how the system performs, a higher number will improve performance on a loaded system)
Have you tried calling recoverSession? This is supposed to request that all unacknowledged messages be redelivered, without having to close the session and open a new one. I don't know if it guarantees in what order the messages are redelivered.