Сомневаюсь что именно загрузились несколько тысяч. Скорее всего загрузились 50 самых новых.
По Вашему вопросу
Всё дело в выделении, "выделить все" на самом деле выделяет только видимые на экране, чтобы не было неприятных сюрпризов.
Это можно поменять: настройки программы - список сообщений - выделить "все" означает... выбрать "все загруженные".
---
Но если Вы хотите удалить много-много старых писем, то это проще и быстрее сделать в веб-браузере на сайте Вашей почты.