Должны удаляться все сообщения, которые хранятся на устройстве, то есть "все" - это условность, специфика мобильной программы, которая не загружает все сообщения.
Но вот хранение на устростве - это по умолчанию 250, так что что-то все равно не так, если Вы не меняли эту настройку ("хранить сообщений..." в "доп. настройках и папках" учетной записи).
Проверьте, пожайлуйста, и при необходимости напишите на kmansoft / собака / gmail / точка ком.