Thanks for all the responses!
It ended up not being quite as painful as we thought. We printed a list of the largest mailboxes and handed that out to department heads. We then gave them a generous two weeks to clean out voluntarily. After the 2 weeks, we set the limit such that anyone with an oversized box could receive, but not send. People started cleaning up at that point. Later that day, we ran the cleanup agent to move all mail older than 2 years to the system cleanup folder. We had told them previously that this would happen. A couple days later, we ran it again to delete the cleanup folder.
The main problem we experienced was people unable to archive for whatever reason, requiring a site visit. We had a few under the impression that their email belonged to them and they should be able to keep all of it and take it with them when they retired (we really had someone say that). We reminded this person that, in fact, it was NOT their property.
All in all, it went pretty well.