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.