I'd second "use the thunderbird archive" and add "use IMAP."
Thunderbird can archive mail into a single folder, or per-year folders, or per-month folders. When you are using IMAP, those folders are on the server, and accessible from any client. All of the clients I'm aware of allow you to "subscribe" or not to folders of your choosing, and most offer more fine grained control to choose what to download and keep locally in order to control client storage and bandwidth use.
Thunderbird has an excellent search engine built in, so searching is straightforward.
Thunderbird also supports IMAP tags (labels), so you can apply an arbitrary number of tags/labels to each message. This is a lot more flexible than sorting messages into folders manually. Once you start tagging messages, a clear and simple workflow becomes clear:
Your inbox should contain only messages that require you to act on them in some way. Once a message no longer requires action, tag it if necessary and archive it. Or, if it is definitely not required, delete it.
Simple. Now your inbox is cleaner, you'll spend less time sorting mail, and a lot less time searching for it. You can unsubscribe from older archives if you like, or simply choose not to keep them locally to save disk space on the client.