Если сообщения удаляет клиент, то скорее всего никак, хотя могу предложить произвести проверку сообщения по фильтру message_id, если id отсутствует то и удалите запись из бд, но я не уверен, что после удаления сообщения клиентом телеграм удаляет и само сообщение у себя с сервера, тем не менее думаю проверить стоит.
В случае, если вы удаляете сообщение ботом то тут и так все должно быть понятно.
