This is not just when you delete email, it also occurs if you move the mail to another folder. It appears beagle's index does not get updated when you either move or delete email. -- Beagle remenber deleted evolution emails https://launchpad.net/bugs/50842