The 16Gb max size is for Exchange 5.5 standard the Enterprise edition is unlimited. To reduce the size of the priv.edb you need to run a backup, Then get your users to empty their deleted items ( why they want to keep deleted items from 2yrs back is baffling), empty or archive the sent items, journal, Inbox etc dump some of the 10 Meg AVI and MPEG they keep sending to everyone, and generally get rid of the garbage they keep (You can use the cellar\garage\loft analogy to explain it to them).
Then you can backup again (online and offline) stop the services and run Eseutil in defrag mode to compact the .edb ( full instructions on using Eseutil on the MS KB ) This operation can take a long time and your mail server will be down for the duration.
Another option would be to backup up (Offline) then to restore the services and use Exmerge to copy all the mailbox data to .pst files ( you will need maybe 40+Gb H.D. space to store them) then export your directory, stop the services and delete the priv.edb and the log files, When you restart the DS and IS a new empty priv.edb will be created, You can then Import your directory to recreate mailboxes, DL etc and use exmerge to copy the .pst file back into the database. This is a LAST RESORT method as multiple smtp addresses are not always rebuilt and server side rules can disappear
As always eseutil is not to be used as general tool. It is for specific problems and misuse can cause loss of data (Hey I,m sounding like MS PSS staff)
Hope this helps
Chris