I Think it's just the nature of IMAP email clients - when you delete the email, it just gets flagged for deletion, and won't actually push the delete. When you purge messages marked for deletion, it should push those up to the cloud and down to the phone.