What I did not mention in the post above is that we use a network of two brokers in order to fulfill high availability requirements and that the client was retrieving messages based on a message-selector (JMS-CorrelationID).
After several tests and tracings even on TCP level we were able to track the problem down to a broker-network-issue. If no network was configured, no message loss occured. By checking the documentation again, we found a section which pointed at a possible issue with networks of brokers and message selectors: http://activemq.apache.org/networks-of-brokers.html#NetworksofBrokers-Conduitsubscriptionsandconsumerselectors
Disabling conduitSubscriptions in the bridge-configuration made our message losses disappear:
Probably this helps someone else.
Edited by: tom.guenter on Dec 23, 2011 11:21 AM