А учётка настроена через IMAP (я надеюсь... POP3 с Яндексом не надо)?
Не удаляются это как, сначала перемещаются в Удаленные а потом возвращаются после проверки почты?
Нужно проверить что для папки "Удалённые" правильно задано соответствие папке на сервере.
- Длинное нажатие на учётке - доп. настройки и папки - папки.
- Дать обновиться списку папок
- Найти "правильную" папку Удалённые на сервере (кажется у них так и называется), нажать на имя папки, выбрать "Синхронизировать с Удалёнными".
