Disk space doesn't matter. That's going to be mostly extra headers and formatting and attachments. I can't find many sources for the number of words in an email, but what I did find suggests about 50. Let's assume that's an entire order of magnitude off, and you have 500 words * 5800 emails. That's 17MB. A laptop or a phone can easily cache that much data and search it in a tenth of a second. All you have to do is filter out the junk beforehand instead of repeating the work every time you search.

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.