I've found that it entirely depends on your agency. If you have an environment where you can dictate policy and training, having a 2 or 3 gig mailbox is more than generous; you would need to keep at the users to get them to back up old mail and archive it offline to a storage area though for regular backups.
Make it larger and in some cases you'll have users that start using your mail server as a way to store all their documents, like an uber-convenient disk storage cloud.
If you don't have the ability to say "this is how it is", you're going to have administrator and people who outrank you dictate they want XYZ to work the way they want it to work regardless and probably will abuse it.
Do you have a mail system in place right now? What are the users currently using? What are the current statistics? That should form the basis of your estimates.
Usually if you set a big limit...5 gig, perhaps...you're going to have a small percent who abuse it and will climb as high as possible, while most will use only a fraction of that space.
I'd look at your current usage patterns and see if you can get a rough estimate from that. Otherwise, get a terabyte of storage (if email is an important function, the cost of a good backup system and storage of a terabyte isn't much, even adding in RAID).
Last look at your data retention requirements. You don't say what agency this is for, but depending on the field there may be laws dictating what has to be retained and for how long. You'll need to factor that into your backup and storage strategy as well.