I get that if the ejb.jar that I'm deploying is dependent on a different jar that has not been deployed yet.
Try removing just this ejb.jar, start up jboss(wait for the full/clean start up), then drop your ejb.jar in. If you don't see this problem, then its a deployment ordering issue. If you do...
the problem is that I don't have all classes in the deploy-directory, I have also some libs in my classpath. The JBoss-Server is not able to find the classes from the classpath...
And the classpath I set is definitely correct.
The package-structure in the jar in the deploy-directory of the server is identical to the package in the jar from the classpath. Could this be a problem?
Using the system classpath is definitely not recommended with JBoss.
I agree, classpath is a "no-no". Your choices are simple.
Place the jar in the server/default/lib directory
You could choose the jboss/lib directory as well. I'd prefer the deploy directory for the hotdeployment feature, or the lib directory if you don't plan to hotdeploy.
put everything in the deploy directory, as ioparra told you. I would suggest another way: deploy an ear with all your jars. Use the Class-Path of the manifest of your ejb jar.