Ref T6615. Mixing ASC and DESC ordering on a multipart key makes it dramatically less effective (or perhaps totally ineffective).
Reverse the meaning of the priority column so it goes in the same direction as the id column (both ascending, lower values execute sooner).