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 is 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.

----

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.