Thanks Mark Roberts for the clarifications.

If you have your application deployed on a server that is also running HornetQ, it would fail every time.

You mean the same server running your application as well as running the JMS queue via HornetQ? That's what I had in mind as well. As said, I would expect in this case that HornetQ starts first, maybe that is not the case. I need to have some way to reproduce this first, to see what's going on.

It would be unreasonable to expect a user to undeploy their application to successfully restart their server and then redeploy it again.

Absolutely, no doubt about that.