Shouldn't the messages queues map, actually be a concurrent one? private final Map<Object, MessageQueue> messageQueues = new HashMap<Object, MessageQueue>(); /Heiko