The most common cause for this is that you have selected to Hide Deleted Messages. When you click this button, the messages you have selected to delete are hidden - but not removed from the server and therefore, they are still taking up your server space. To confirm this, Click Hide Deleted Messages button again. It will toggle back to Show Deleted Messages and you'll see all the messges you previously marked for deletion. The only way to permanentely remove messages from the server is to click the Purge Deleted button.