I think that you should post destinations-service.xml files from both nodes to give more information about how those queues are created. I assume that you've set up them as clustered and post office to be in cluster mode (databasename-persistence-service.xml) and you don't use HSQLDB in cluster mode.
Solved - As it seems the problems was in deed the HSQLDB. Somehow I missed that it is not suited for a clustered environment. Thanks.