I have one big "Archive" folder, unsorted and I had the same issue as you are worrying about with finding emails, and regularly couldn't find emails I knew I'd received. I used to resort to displaying all my emails in date order or by sender name and find it myself, but a couple of weeks ago I downloaded Copernic Desktop Search. I've seen loads of recommedations for it, and when I first started it up I set it to search my two IMAP email account folders as well as all the hard disc folders where I keep files. I think that so long as you're online it will search them. The only issue I've had with it is that initially it slowed my machine down quite a lot, as it indexes all the files already on your computer when you first get started, but it's been a couple of weeks now and other than a slightly slower boot up it all seems fine. It's free so might be worth a go just to see if you like it. But consider leaving it alone to index for a few hours when you're not desperate to use your computer.

One thing that I do which I think is pretty useful is to archive emails on completed projects (particularly events I've organised or trips I've been on) into separate folders just to get them out of the way. If I do decide to go to Beijing again or organise another ball then I can get to the emails again, otherwise I don't have them cluttering up my regular archive folder.