“There is no spoon”.
Mailbox quotas is only part of the solution. You also need to reset user awareness and expectations, also implement a centralized e-mail archival solution (if needed or desired).
You need better trained users. First of all, Exchange is not a filing system. Typically, the most space is consumed by attachments. To minimize this impact, users should be trained to remove attachments from messages and delete messages that they no longer need. This can be enforced using mailbox management and third-party archiving/retention solutions that replace messages with shortcuts and/or make them available in another manner, such as a Web portal.
Until attachments and old messages are deleted by users, or they get removed for them, you will constantly battle with an ever increasing information store size. In the meantime, things that you can try include breaking users into additional storage groups and databases to reduce the size of each. This will also lead to faster backups/restores of each storage group/database.
It’s also worth considering that archived data, including e-mail presents a legal liability. You cannot control .PST files in the same manner that you can a centralized/managed archive system.