Добрый день!
Версия 1.6.2.9, HTC One M8, Android 5.0.1
С недавнего времени письма, при удалении их на телефоне, удаляются только локально. На сервере они так и остаются в папке Входящие.
Настройка Deleting messages для каждого аккаунта - Move to Deleted folder first.
Стоит отметить, что это начало происходить несколько недель назад, после очередного обновления программы. До этого было все нормально.