Может ли бот удалить все свои сообщения с пользователем?

Простейший пример

from telebot import TeleBot

BOT_TOKEN = "<your_token>"
bot = TeleBot(BOT_TOKEN)

users = {}

def add_msg_to_list(uid: int, msg_id: int):
    if uid in users:
        users[uid].append(msg_id)
    else:
        users[uid] = [msg_id, ]

@bot.message_handler(commands=['del'])
def cmd_start(m):
    add_msg_to_list(m.chat.id, m.message_id)
    for message_id in users[m.chat.id]:
        bot.delete_message(
            chat_id=m.chat.id,
            message_id=message_id,
        )
    users.pop(m.chat.id)


@bot.message_handler(func=lambda m: True)
def any_msg(m):
    add_msg_to_list(m.chat.id, m.message_id)


if __name__ == '__main__':
    bot.polling(none_stop=True)

Думаю основная идея понятна. На каждое сообщение юзера сохранять message_id этого сообщения и при необходимости удаления истории, использовать этот список. Так же не забывать после удаления истории очищать список с message_id.