If the callback throws an error, none of the awaiting coroutines will run, and adding a catch would break the callback error propagation.
Also, nobody said that we need callback error propagation in a priority queue to act the same exact way that callback error propagation works in a straight promise chain... but if you just want to reject all waiters in case of an error, you can do that.
Take a look at sindresorhus' p-queue project - https://github.com/sindresorhus/p-queue - which is about 40 lines of code that take care of queueing exactly the way you want. And it's easy to modify if you want to reject the whole queue in case of an error, which is something that I've done myself in the past. You can see them discussing the possibility of that feature right here - https://github.com/sindresorhus/p-queue/issues/29
Long story short: Your problem is with ordering, not locking.
> Long story short: Your problem is with ordering, not locking.
Look up the definition of a concurrency lock.