The problem you're facing is as much political as it is technical, and you're positioning yourself to be the bad guy. You can get out from under by shifting part of the burden onto your users, and enlisting their help. Make the case now that service is going to deteriorate as the organization scales unless people can limit the amount of email they keep on the server, and ask your users what they think a reasonable retention policy might be. You won't get answers from everyone, and some folks will complain, but if you get a couple of good answers, you can always say "we asked, and the answer was X" if people complain later.

You'll still have technical problems to deal with, but setting reasonable limits now might give you some more breathing room.