I have a million emails occupying 20GB, and receive several hundred per day. I search my mail archive using xapian (via notmuch) on my laptop, but such solutions are less practical for phones and even some desktop users expect IMAP search to work. Indexing is definitely a problem if you want the server's store to be encrypted.