The reason is as follows: the default JobExecutor has this:
protected int maxJobsPerAcquisition = 3;
This means that the acquisition thread will try to fetch 3 jobs at once. Suppose now we have 2 job executors.
The first one fetches job A,B,C. The second one B, C, A. They both try to lock it in that order. It's easy to see why this leads to a deadlock.
The solution (without impacting existing code) is simple: make the default for maxJobsPerAcquisition 1 instead of 3. That way, only one row will be locked per transaction and no deadlocks can occur.
It does mean that performance will be a bit impacted (3 transactions + queries vs 1 before). But correctness beats performance any time.