I've deleted a lot of my messages but I still seem to be over my legacy email (Cyrus) quota.
Answer
Some possible reasons:
You may not have successfully Purged the items you have marked for deletion.
You have deleted numerous small messages but one or more large ones remain.
New messages that were waiting to be delivered have now arrived and filled up your inbox again.
You have left an email session running on another machine which is preventing your account from being updated.