Вероятно, Вы настроили Яндекс через POP3?
Если так, то просто удалите учетную запись и добавите заново, не меняя настроек серверов (то есть просто введите адрес и пароль и нажмите Вперед).
Будет использоваться IMAP, и ситуации как Вы написали не будет.
А если сейчас IMAP, то проверьте соответствие папки Удаленные в программе и на сервере.
- Длинное нажатие на учетной записи
- Доп. настройки и папки
- Папки, дайте обновиться
- Короткое нажатие на серверой папке Удаленные --выберите "С папкой [ Удаленные ]"
И пока не вышли отсюда полностью:
- На один экран назад (Доп. настройки и папки), затем вперед в Доп. настройки
- Убедитесь, что включена галочка "Синхр. удаления с сервера"
