Just wanted to let you know, that I finally found the cause for our problem.
It was related to the Binding Service that maps the JBoss ports to different values for several instances. This includes a mapping for the Messaging port as well (also see http://www.jboss.org/index.html?module=bb&op=viewtopic&t=86625 ).
The mapping definition contains the piece of code that is described as changed under item 3. of the JBoss Messaging 1.0.1.SP2 release notes ( http://www.jboss.org/index.html?module=bb&op=viewtopic&t=96679 ).
I added the two lines from the release notes to the mapping code and now the error is gone.
Nice catch :)