If you can remember a term, any term, that was written in the message, you can search & jump to it directly. For my girlfriend and I, it was the bar we went to on our first date. This feature only gives you small subsets (a couple dozen, maybe) messages near the query result, but then you can just search for the last message again and get the next “page,” so to speak. Of course, remembering such a term is hard, which is what I assume you mean by “search for old messages is unreliable,” but it’s at least a possible workaround.