А на что повлияют эти условия?
Вроде бы продвижение в очереди оценивается по времени стояния. При этом не столь важно сколько времени ушло на каждый шаг.

Тогда нужно определить задачу поточнее   

Интересно рассматривать случай, когда поток сообщений слегка "заваливает" очередь сообщений. То есть система обработки сообщений уже не справляется с нагрузкой, и очередь медленно растет, но ресурсы системы позволяют жить в таком состоянии достаточно долго.

Примерное определение приоритета:
Приоритет означает, что при "заваливании" очереди сообщениями с приоритетом 10 и 1 на каждое обработанное сообщение с приоритетом 1 будет обработано 10 сообщений с 10-м приоритетом.

Итого, задача:
 Устроить все таким образом, чтобы сообщение с любым приоритетом не "застревало" в очереди навечно, при условии примерно равномерного "заваливания" очереди сообщениями с разным приоритетом.


Можно предложить "поиск в глубину". Все сообщения вставляются в конец очереди. При изымании сообщения из очереди будем просматривать X сообщений в глубину очереди и искать среди них сообщение с максимальным приоритетом. У всех сообщений, которые "пропустили" свою очередь - повышать приоритет на 1. Так получится, что очередь будет двигаться, приоритет примерно будет соблюдаться и расходы на обслуживание очереди не будут зависеть от величины очереди.

О том и речь...

Допустим, некое сообщение категории "нахрен не надо" приходит на обработку. В полночь... очередь - на 8 часов. Соответственно мы назначаем этому сообщению время обработки 8:00... время идёт... и вот 8:00... и мы обрабатываем именно это сообщение, несмотря на то, что в очереди подпрыгивает парочка секунду назад пришедших сообщений с пометкой "супер-пупер-гипер-срочно".

Это при условии, что очередь не переполняется. Если же она переполняется, вместо времени вводим синтетику, которая позволяет дробить любой интервал, тем самым устанавливая нужный порядок обработки. Или, как вариант (который мне лично нравится меньше), вводим динамическую важность сообщения, которая зависит от исходной важности и времени сидения под дверью кабинета обработчика.

Главная идея - если было принято решение, что сообщение А обрабатывается раньше сообщения Б, то это решение окончательно и ничем не может быть изменено.

Так, вроде бы, формула 
p = ( L * (t - t0)/(tl - t0) ) * K / k 
и обеспечивает отсутствие застревания для любого, даже самого медленного, элемента. 
С одной стороны мы забираем элементы и знаменатель (tl - t0) все время уменьшается. 
С другой стороны, каждый следующий элемент добавляется через какое-то время после предидущего. Значит t все время растет по сравнению с постоянным tl(i) некоего медленного элемента. 
Рано или поздно даже элементы с самым большим приоритетом будут встваляться после этого i-того медленного.