Try using a factory to create the instance, where each EJB gives an identifier and the factory returns an instance based on that identifier. Sort of what the logging frameworks do when you lookup a logger.
Another alternative would be to place your shared JAR file into an EAR and use an isolated classloader. For example, EAR1 contains utility.jar and ejb1.jar, EAR2 contains utility.jar and ejb2.jar. And make the utility class a singleton.
There are probably other ways, but these two seem most appropriate.