Мне нравится использовать один поток (или поток пула) с ResetEvent (вручную или автоматически) с тайм-аутом, установленным на некоторую долю самой быстрой задачи (скажем, раз в 5 секунд). Внешне вы можете вызвать событие, чтобы обработать ожидающие отправки, или каждый раз, когда истекает время ожидания, вы также можете проверить наличие ожидающих отправок.
Если вы установите тайм-аут на долю (скажем, 30%) наименьшего интервала, то вы сможете сохранять приличный контроль над тем, сколько времени занимает процесс «проверки», но если вы пропустите интервал, у вас будет разумный период времени в котором для отправки задачи. Это также дает вам окно разумного запуска.
Реализация может быть осуществлена путем ведения упорядоченного списка того, какой вызов API должен произойти затем, и установки времени ожидания в некоторой части этого.