Alibek B.На самом SMS-сервисе отменить сообщения и отправить новые я смогу без проблем.

Т.е. есть возможность отслеживать прохождение каждого отдельного сообщения ? Если брать за ключ сообщения его номер телефона, на который оно отправляется.
Если состояние к/л отслеживается - ничего нового в программировании состояний нет. Обычная Protocol State Machine. Применительно к мутонам данной задачи:
1. Заводите таблицу, куда будут складываться отобранные для отправки ключи: (Клиент, Услуга, Дата списания), например, как уже предложили, или что там бедут таким уникальным ключом;
2. Таблица с ключами имеет Foreign Key на таблицу сфоормированных сообщений, в которой первичный ключ - номер телефона;
3. Соответственно при каждом запуске задания по отбору новых ключей для сообщений - исключаете из выборки все, что уже присутствует в таблице из п.1;

Ну а на таблицу из п.2 вешаете собственно состояния и тайм-фреймы протокола. Расписываете сначала - какие состояния есть у сообщения. Тут все зависит от того, как идет общение с шлюзом отправки SMS. Может, например, после формирования сообщений из курсора приходится ждать некоего "планового окна отправки сообщений." Т.е. будут состояния: "Сформировано, ждет отправки оператору", "Отправлено оператору", "Оператор принял сообщение в обработку"... Все по факту - как там идет обмен и какие данные доступны с той стороны. И для каждого состояния назначаете свое предельное время жизни, которое и фиксируете в таблице из п. 2.
Дальше либо все проходит тип-топ, тогда данные из таблиц пп. 1, 2 уносятся в архив и перестают работать фильтрами для последующих задач по формированию. Возможно, при этом действии в исходных данных, откуда формруются сообщения, проставляется watermark: по дату <ДД.ММ.ГГГГ> (или по ключу расчетного периода, старшего в группировке) все услуги обработаны.
Либо происходит тайм-аут и в зависимости от состояния сообщений принимается решение - где что почистить (и где отразить факт отмены обработки), что-бы процесс пошел снова.