Никаких багов тут нет.
Дело в том, что сообщение удаленное из папки "удаленные", как бы насовсем, реально лишь поемчаются в базе писем как "стертое письмо"
Чтобы полностью, насовсем удалить их - надо произвести операцию "сжать папку" над тем почтовым ящиком, где вы "удаляли мессаги".
Кстати, для примера, Виндоус при удалении файла из корзины тоже не производит физического затирания файла с винта.

Как уже сказал Merlyel - это совершенно стандартное поведение почтовиков, почти всех, я думаю.