Откуда берётся идентификатор, по которому сервер понимает, что повторно отправленное сообщение уже было сохранено?

Идемпотентный идентификатор обычно создаётся клиентом один раз перед первой отправкой и сохраняется для всех повторов той же операции.

Сервер связывает его с пользователем/чатом и уникальной записью, возвращая уже сохранённый результат при retry. Новый ID на каждом повторе разрушит дедупликацию. Случайный client ID не является полномочием: доступ к чату и допустимость payload проверяются независимо.