My 45,000+ messages take 170mb. I've been using Remail for a few months now and find it indispensable. For an idea of how useful it is to me, I sort my apps by frequency of use and reMail is on page 2 of 6, after OmniFocus but before Mint.com.
It's one of those apps I didn't know I needed but use all the time now that I've got it.
Out of curiosity, how do you track frequency or recency of use? Just remembering, or is there data to be found?