Have you tried retrieving your email via a POP3 client? If you can do this, and have your client set to remove mail from the server, you can not only get your mail but free up the mailbox storage space at the same time.
Often, once this has happened, you can then successfully log-in to webmail (may have to wait till the next day for the quotas to be re-read). Once there, make sure you also check your "old-messages" folder - often they are rolled into there after a time but since you are not "subscribed" to that folder by default, it is easy to forget to deal with them.
You also may be able to access your mail for deletion purposes via the shell using pine or mutt.