Are you using the Standard version of Exchange? This has a 16 GB limit on the size of the store. Or are you using the Enterprise Edition, which does not have this limit, and you are running out of disk space?
The first would be resolved by setting some limits on the users as to the size of their mailbox and size of messages allowed to be sent and accepted. Not a popular move, but one that may be necessary.
You would probably want to institute a policy to delete messages from the deleted items folder after a period os so many days. You’d be surprised how many people ignore the deleted items folder, and jsut let it grow. There may be other folders you may wish to set a retention policy on as well. If you have a spam filter that places all purported spam in a folder, you might want to dlete messages left in there after so many days as well.
If you are runnig out of disk space, well, this is an entirely different problem that can be resolved by moving the store to another, larger, disk.
Another thought that just occurred to me is your Exchange backup. You do run one, don’t you? If you are running out of space due to logs, then the backup is not doing its job. The backup should be set to delete the logs after the backup has been done. The backup would commit the logs to the store and the logs are then no longer needed.
I’m sure there are a few other scenarios, but the other half is on my case to get ready so we can take her father down to see the cherry blossoms.