I hope your company has really thought this through. A lot of business email really should be preserved for legal or financial reasons.
That being said, there are three ways that I see to go about this:
1) Institute a third-party archiving solution. There are a number of them out there; I have no recommendations. Often these solutions can greatly compress the mailfiles to make the available space last as long as possible. This has the advantage of being able to be backed up and thus protected from failure at the user/workstation level.
2) Use the archiving tools in Notes. Archiving can be done to a network drive, another server, or the user’s local computer. It can also be set up to run automatically. The problems here are that it does have to be set up on each computer individually (some savvy developer might know a way around this) and if you use local storage, there’s always a possibility that a crash or reimage will wipe out everything — this can be real chancy if you are talking about documents with a legal and/or financial impact. Running it on a network drive or another Domino server allows you to back it up, but may not give you any significant cost or space savings.
3) Replication, either locally, to a Domino server or to a network drive. Very much the same advantages and drawbacks as archiving except that if you set up this up to a backup or failover server, you can programatically replicate everybody with administrative tools and never have to touch individual workstations.
I am extremely wary of blanket deletion policies. There are too many legal and financial ways for this to turn out to be a real problem for a company.