Ein Lösungsansatz könnte sein, die Liste nur beim Hineinschreiben (sehr schnell) und beim Löschen aus ihr (auch sehr schnell) zu sperren. Während der Abarbeitung des Jobs kann die Sperrung schon wieder aufgehoben sein.
Ich kann mir kaum vorstellen, dass es dadurch zu nennenswerten Verzögerungen auf einer der beiden Seiten kommt.