I run qmail for sending/receiving mail (on Gentoo; netqmail package), using maildir, of course. On top of that, I run the Courier IMAP server on my internal network (with TLS encryption). Until a few months ago I used Mutt as a client (console-based), but I've moved to using Roundcube (web-based email), which I initially installed for my wife, and have been happy with it. I also have some automatic filtering to folders via Maildrop (another Courier utility; it looks at a ~/.mailfilter file to route mail).
Roundcube/the IMAP server's search is OK most of the time - I keep my inbox small and move older mail to sub-folders - when I want to do advanced searches or search large mailboxes I log in and grep through folders of interest; this works well with the maildir format with one file per message. Maildir was also quite resilient when I had a HD crash and needed to recover some lost mail (block scan for blocks that look like mail headers found most missing items, and I do better backups now - mail is under ~/.maildir and gets backed up automatically).
I would move older messages to maildir (there are plenty of mbox converters, and almost anything non-proprietary should be convertible to mbox or maildir via existing programs or a short perl script) - even if at some point maildir dies off entirely, which seems unlikely, converting it to another format will always be trivial due to its simplicity and it has the advantages mentioned above of being able to search easily with grep etc.