We have found a work around.
Originally we specified that the email would be deleted and copied to a sub folder.
After we changed this to mark as read only and not move. The problem goes away.
It seems the bug is that the email is not marked as deleted the first time the trigger fires, but the second time it does get moved.