PS: this is a very simple configuration, stand-alone, non-clustered with 1 JMS sender and 1 JMS consumer on the same server as the hq instance. No paging configured, only customization was increasing min/max heap.
PSS: The only thing I think would be odd from your perspective is that the clients are still using the IBM JRE 1.5 like some of the other posts and that one problem that was put into JIRA already about class-not-founds.
The only scenarios I've seen this happening was when the client was killed, and TTL was too high. If you probably waited TTL, the messages would then be delivered: