It seems to have settled down over the past few days. It's pretty rare that a message gets stuck and it has been running solidly for several days now. We didn't really change anything but if I find anything to suggest why it suddenly got a lot better, I'll come back to share!
Thank you for your help! If we end up at the same spot with messages being stuck, I'll be sure to look into the JBM or HornetQ upgrades.