In order to delete e-mail messages, once your "over quota" grace period has expired, you will need tomake sure that your e-mail client is configured to actually delete messages when deleted and purged, not just moved to another folder.
Using the Webmail e-mail client as an example, you will need to:
Until your disk usage drops beneath your quota limit, you will need to truly delete messages. Once you are under your quota, you may once again use your previous "delete" configuration.