We had the same problem with Exchange 2000, users mailboxes would get too large and the Exchange Server wouldn't cope.
The eventual solution was to upgrade to Exchange 2007, some users have a legitimate need for long term archiving and archiving these on the server (and having IT take care of backups) is more reliable than having an archive.pst that could be wiped out with a disk crash.
Our CFO for example recently lost 5 years worth of archives in a disk crash, as they have been archived off of the server and onto his local PC - our server side retention policy (due to Exchange 2000 limitations) was 3-months, when anyones mailbox started to approach the 1Gb mark the IT staff would go have a chat and archive the mail off themselves if required.
If upper management lose any email or archives, it doesn't matter what the 'policy' is, the IT staff will end up shouldering the blame. If you explain things clearly to management, chances are they'll make room in the budget for improved email retention if it makes their lives easier.