1 - Удалять нужно способом "переместить в папку Удалённые" ("удалить сразу" обрабатывается сервером Gmail как "снять ярлык, оставить письмо").
2 - Проверьте пожалуйста, что папка Удалённые в программе соответствует правильной папке на сервере:
- Длинное нажатие на учётке на главном экране
- Доп. настройки и папки - папки
- Дайте обновиться, найдите [Gmail] и под ней папку Корзина (также может называться Trash или даже Bin)
- Нажмите Корзину, выберите "С папкой Удалённые" (имеется в виду "синхронизировать с папкой Удалённые")
- Вернитесь / закройте, попробуйте переместить в корзину, теперь должно сработать.