Are your messages persistent?
Thank you Yong. I don't think they are and that's probably the source of my issues! I'll reply here once I confirm that they are not and that sending persistent messages resolves the message loss.
The queue has to be durable
producer's delivery mode is persistent by default
message jms delivery mode is persistent - or the message is durable
your hornetq broker has to turn on persistence support
I don't need to explicitly set the message delivery mode, as I use session.createByteMessage(), which internally create a durable message.
That was it. Setting the header 'persistent' to 'true' on every message seems to have fixed the issue.