Из самой документации IMAP:
Номера сообщений IMAP4 меняются при изменении почтового ящика;в частности, после того, как команда EXPUNGE выполнит удаление, остальные сообщения перенумеровываются.Поэтому настоятельно рекомендуется вместо этого использовать UID с командой UID.
Обсуждение на SO: Об IMAP UID с imaplib
IMAP4.fetch(message_set, 'UID')
Выборка - лучший способчтобы получить UID сообщения
И чтобы получить идентификатор сообщения, вы можете сделать что-то вроде этого, хотя не все сообщения могут иметь идентификатор сообщения.
server.select(imap_folder)
# List all messages
typ, data = server.search(None, 'ALL')
# iterate through messages
for num in data[0].split():
typ, data = server.fetch(num, '(BODY[HEADER.FIELDS (MESSAGE-ID)])')
# parse data to get message id