VavNat
Еще сделай сжатие папок. Наверное, это никогда не делалось и что сейчас творится в базах неведомо никому.
А лучше вообще зайди в меню "папка", выбери "управление", отметь все чекбоксы и запусти. Там и удаленные письма окончательно удалятся и сожмется база и, если она кривенькая уже, то починится заодно