Not sure where to put this comment, but one of the challenges I have right now is that I use an "inbox+archive" folder, where the inbox has unprocessed mail, and the archive is everything else.
It makes looking for antecedents of an unprocessed mail quite hard. Not sure how to describe this use case, but it is certainly common for me.
I think what you're seeing is a problem of having strict folders. The conversations are more important to people compared to strict folder hierarchy. If you're looking at an archive folder we should be able to show you messages that are part of the conversation thread but reside in other folders. The folders are there to help process mail and not create problems for viewing conversations, we should be taking that into account. Not sure this is relevant to search... :)