We are using some HASingletonServices. These services use the HAJNDI tree to lookup other services.

Both the HASingletonservices and the HAJNDI service are notified if a node (eg the master) is removed from the cluster. However, the order seems to be random. If the master goes down, the HASingletonservce seems to be notified first. It tries to start the singleton on another host. While starting, it uses the HAJNDI, but this one still tries to connect to the old server, leading to NamingExceptions.
Since i added a jmx depencency from the singleton service to HAJNDI, i would expect that the HAJNDI gets notified first. That would fix my problem.

I looked in the code of the DistributedReplicantManagerImpl and it seems that this one does not keep track of the order in which keys are registered. I quickly changed all HashMap and HashSet instantiations of this class to LinkedHashMap and LinkedHashSet instantiations, and now my problem is fixed.