At work I use mail.app on my machine which pulls email from an Exchange server. For some reason we have relatively small mail limits and I don't think they are going to be increased anytime soon, so occasionally old email needs to be purged. This should be a best practice anyway because I am sure 60%+ of your email has no need to be stored after one month.
An issue with mail.app is that there doesn't seem to be an easy way to view an entire mailbox (all folders listed in one view), if I was able to view this I could easily sort by size and delete the worst offenders.
The workaround is to target the folder that is the largest and then find the largest emails within it.
To do this right click on the mailbox that is full and click get account info.
The first time you run this it might take a minute or two to calculate all the folders but once it has you can sort by size and use that as the basis for your email hunt.
A more permanent solution would be to think about the email you are saving when you process your email and only keep mail that you think you will need - especially if people are sending files.