It is suprising how slow this can get if you do not clean up after you.
How many messages have you deleted and not emptied the deleted box?
How many messages have you with attachments that are large?
When you have deleted the files use the clean up facility by clicking on tools/options/maintanance then click on the "clean up now" button.
Hope this works.