Este é um problema de transação - basicamente, sua combinação de cliente e servidor não tratou o movimento como uma transação.
Eu acho que depende mais do cliente do que do servidor, mas o servidor IMAP que eu conheço é strong no banco de dados, sendo baseado em PostgreSQL , é Archiveopteryx . Talvez ele trate melhor com o lado do servidor, mas provavelmente não fará nada por você se o problema for do lado do cliente.