Yeah, what I have discovered is that in WAV format, each 15 minutes of audio is about 20MB... Switching to MP3 is significantly smaller, but the time to encode a file is around 2-5 times longer from what I have seen, the longer the message the longer it seems to take per minute of recording to encode.
I will probably try switching a couple mailboxes to MP3 format and see what happens... There are only 3 or 4 people in this company that do long recordings, so if it works for a couple of them, it should be fine to implement on the others.