If you're using Spring to autowire your EJB clients, it's quite easy to configure the service so that the home interface will refresh on connection failures. Note that if you're using EJB3, you will need to upgrade to at least version 2.5.5 of Spring. There is a bug in earlier versions of Spring which prevented this technique from working with EJB3.
In your spring file, make sure you configure your slsb references to have cache-home disabled, and refresh-home-0n-connect-failure thusly:
<jee:remote-slsb id="myService" jndi-name="MyService/remote"
<!-- Include any relevant environment settings here -->
With this, you should be able to restart your EJB hosts without needing to restart your EJB clients!