I too have been having trouble with the same problem. The solution I have come up with is a bit easier to manage than ensuring home + remote interfaces are in each jar (after all you could hava many jars!).
Why not try creating a single "EJBinterfaces.jar" which contains all your interfaces. Drop this into jboss\lib\ext and it will be available to JBOSS as it starts.
BTW, I also tried adding my development directories to the CLASSPATH, and JBOSS_CLASSPATH in the run script, but this just caused deployment problems. If anyone has a better solution please let us know!
Just found another way from looking on the Forum.
In the Manifest.mf file add the line "Class-Path: name-of.jar". This will point jar A to the contents of Jar B as long as they are both in jboss\deploy. I have tried it and it works.
To get the jar tool to keep the edited manifest.mf file use something along the lines of "jar cfm name.jar META-INF/Manifest.mf *.class" to force the jar tool to keep the current manifest file. If you have no manifest file, extract the one the jar tool creates for you from the jar file using zip, then edit that one.
Hope this helps (and that you are still monitoring the forum!)
Can you control the order of the deployment? In my case, ejb A makes reference to ejb B. But since A gets deployed first, it never finds B and the deployment of A fails.