**predictable ordering**

In your problem Specifications you included

- if a burst of high priority messages is sent, they should not completely starve lower priority messages (in this regard "priority" is more a QoS level)

which would fit in better with Desiderata, as it is on the vague side.
We don't have numbers on "burst" and "starve", and it's unclear how
to evaluate whether some historic activity trace is correct or not.
I will assume infinite queue capacity,
and that in the long-term offered load shall be less than server capacity,
perhaps due to a throttling layer that precedes our queueing layer or
perhaps due to ability to scale out with unlimited budget VM spawning.

Two priorities, {low, high}, suffice for discussing this.
Suppose we see a random mix of the priorities offered
by a Poisson process, with lambda low enough that the
queues sometimes drain entirely, so we have idle capacity.
In a traditional priority setup we would expect this invariant to hold:

- A low priority task will never be dequeued when a high priority task is available.

This extends naturally to using a great many priority values.

Subject to the requirement above that we sometimes have idle capacity,
we never completely starve low priority tasks.
This suggests that OP uses "starve" in some different way
which aligns to business requirements, perhaps in trying
to meet a Throughput or a 98th percentile Latency
[SLA](https://en.wikipedia.org/wiki/Service-level_agreement).
It may also suggest the input distribution corresponds to
clients executing a {submit request, await response, repeat} loop
rather than memoryless Poisson arrivals.

I propose an alternate specification, simpler than in OP,
which is meaningful to both end users and implementors.

A traditional priority setup can be implemented as a
[heap](https://en.wikipedia.org/wiki/Priority_queue),
with submission timestamps `ts` that are fine-grained enough to induce a
[happens-before](https://en.wikipedia.org/wiki/Happened-before)
relationship between submitted tasks.
We insert the tuple `(-prio, ts)` into the queue,
with a value of the task.
(I negate to finesse the sort order.)
The invariant on dequeues of high priority tasks
is that they pop out in `ts` order, and a similar
invariant holds across low priority tasks.
Sadly they can be starved during a high priority burst.

Suppose both task types always take exactly 100ms to process,
and lambda is low enough that at least once a minute we go idle.
Now, for ten seconds, we add a (non-Poisson) busy client
that injects eleven high priority tasks per second.
During this interval and for a brief recovery period afterward,
we will see zero low priority dequeues, which seems "unfair".
Let's fix that.

Define a fairness parameter, a `gran` scheduling granularity of, say, 2s.
Associate `epoch = int(ts / gran) * gran` with each arrival,
so we might see epochs of noon, 12:00:02, 12:00:04, ...

For each arrival, insert an `(epoch, -prio, ts)` tuple in the queue.
Now we're saying that, within each epoch, the traditional
invariants hold. But if we fail to clear the queue by end of epoch,
newly arriving low priority tasks will get an opportunity to run.
All tasks from prior epochs will run to completion before
we tackle a new epoch.

If that ten-second busy client was going through a
{submit, await, repeat} loop, then the "await" stage
would start seeing larger delays, reducing its offered load.

**retrofit**

Given an existing simple priority queue, e.g. rabbitmq, you could
easily retrofit it with approximately the same `epoch` behavior.

Allocate a (zero-origin) vector of queues.
Define index `active_queue = 0`, where new arrivals always go.
We can always find `alternate_queue` as 1 minus that.
Define `current_epoch` according to `gran`
and a recent timestamp.

New arrivals are thrown into the active queue in the usual way,
and the alternate queue is empty.

At some point we notice that we need to update `current_epoch`
to a subsequent epoch, and we follow this procedure:
1. Unconditionally assign `current_epoch` to be current.
2. Ask whether the alternate queue is empty. Iff empty, toggle the active queue to use it, via `active_queue = 1 - active_queue`.

So at start of each epoch, leftover jobs from
previous epoch(s) are being processed in the alternate queue.
If we are lightly or moderately busy, we toggle
which queue shall be the active one exactly once per epoch.

If we're getting behind, some leftovers will languish
in the alternate queue for more than `gran` seconds,
and we **don't** toggle.
Hence the active queue depth becomes unusually large.
At some point the alternate queue drains,
the epoch ticks over, and at last we toggle.
Since there's an unusually large number of leftovers
that may be from multiple epochs, it may take
multiple epochs for the alternate queue to drain,
even if offered load suddenly goes to zero.
As offered load tapers down, so will queue depths,
and eventually we go back to toggling once per epoch.

In this way we ensure that newly arriving high priority tasks
cannot starve ancient low priority ones.

----

**deadline approach**

Another way to describe fairness is to look at
service deadlines, perhaps retaining that `gran` interval.
For arrivals of either priority, we typically expect
they will be dequeued within `gran` seconds.
Define "starvation" as blowing that deadline.

During a period of starvation where low priority
dequeues happen more than `gran` seconds after enqueue,
reduce the priority of new arrivals.
So an incoming priority of `2` would be reduced to `1`,
and low priority arrivals would be unchanged.

We focus on time spent in the queue,
something this layer exercises control over, since in general
the task execution times could have a long tailed distribution.

----

Here's a **stochastic alternative**.

Define expected task-per-second arrival rates of `lo_rate` and `hi_rate`.
Measure the `lo_actual` and `hi_actual` rates with smoothed moving
average, perhaps using the same exponential decay approach
seen in unix [uptime](https://linux.die.net/man/1/uptime).

When things are "normal", when the actual arrival rate is sane,
we insert `(-prio, ts)` into the queue in the usual way.

During an overload period we randomly knock down high priorities.
Based on rolling a random number, turn priority `2` into `1`,
with increasingly higher probability when `hi_actual`
is increasingly higher than `hi_rate`.

----

**drop policy**

Every physically realized system attached to
the internet will drop requests at some point,
as offered load can always be ratcheted up.
It's just a matter of deciding where the drops
should happen and whether you want to be in charge of them.

Consider specifying and authoring such a policy layer
which front-ends your queueing layer.
Then your queues can confidently plan on never seeing
an arrival rate above R, if that is enforced by policy.