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.