Hi Andreas,
This does sound like an issue we had in the past with jarwrapper and binfmt-support. IIRC, Colin Watson was able to track down the source of this, but at the moment I cannot locate the details of that exchange. It was something along the lines of there being multiple interpreters registered for the given binfmt.
If we know that the user's kernel supports binfmt_misc, then we should be able to figure out what's happening. The output of "sudo update-binfmts --display jarwrapper" (should point to jarwrapper) and "sudo update-binfmts --display jar" (should point to jexec) might be informative. I'll try to reproduce locally and report back.
Cheers,
tony