So it was actually this page which lead me to the solution: Java WebStart slow, requesting libraries from invalid folder
I didn't know about indexing of JARs at all. Now I do. And as soon as I added an index to the JAR, the problem went away!
Thank you all.