There are a few things you could try:
1) If there are not a huge number of tasks, thread off each one and run a 'while(true){Sleep(requiredIinterval);task()};' loop. Lower the priority of the threads running the lower-priority tasks so that they get preempted by the higher-priority ones.
Upside: this simple solution is fairly easy to try and may satisfy your requirements. It is not possible for multiple copies of any task to run.
Downside: The time taken by each task gets added to the const interval, so extending the time between tasks. Not a good solution for thousands of tasks.
2) Same as above, but get the start time by reading wall-time before the task, get the end time by reading wall-time after the task. If (requiredIinterval-(end-start)) is positive, convert to ms and Sleep for that interval.
Upside: The time taken for each task does not impact on the timeout unless it is longer than the required interval. It is not possible for multiple copies of any task to run.
Downside: Not a good solution for thousands of tasks.
3) Implement a delta-ordered priority-queued system. One way to do this is with a custom threadpool class for each priority and one more 'timerThread' to run a delta-queue of tasks. The timerThread class holds the deltaQueue - a collection of tasks ordered by timeout-time and an 'inputQueue' for tasks - - a plain concurrentQueue. The timerThread waits on a semaphore with a timeout set to the timeout-time of the task at the head of the deltaQueue and, if the wait times out, it removes the task, issues it to the threadpool appropriate for its priority and then lops back, gets the timeout-time of the task at the new head of the deltaQueue and waits on the semaphore again. When any of the threadpools has finished a task, it queues the finished task to the timerThread inputQueue and signals the semaphore. The timerThread then wakes up and, since the wait has returned true, it gets the returned task and re-inserts it into the deltaQueue so that its 'interval is restarted'.
Upside: The time taken for each task does not impact on the timeout unless it is longer than the required interval. It is not possible for multiple copies of any task to run. Good solution for many 'timeout tasks'. The tasks just circulate round the deltaQueue, threadPools and inputQueue, so little GC to screw up the timings.
Downside: Complexity compared to other solutions. Not sure if the C# threadpool class allows the pooled thread priority to be set - you may have to make your own threadpool class by passing a blockingCollection to a number of explicit thread instances.
4) All other good solutions that I haven't thought of yet.