It sounds like your EJBs are assuming/trying to do too much at deployment time.
As you've said, [b]at deployment[/b] the dependent EJBs might or might not be up, so trying to "ping" them at this stage is wrong. So, you need to check the dependent EJBs sometime later, either when you have to actually do something or in response to a special "everything is deployed please check your status" message sent to each of the EJBs in turn, manually, after deployment is completed on all 3 servers.
[Message sent by forum member 'matterbury' (matterbury)]
http://forums.java.net/jive/thread.jspa?messageID=322139