It looks like we did not have a deadlock at all, but rather a bottleneck. Using JBoss Profiler (http://www.jboss.org/jbossprofiler) we determined that a bottleneck caused a backlog and since we use Semaphores to enable FIFO processing of messages, the locked threads built up causing the appearance of a deadlock.