OMG, the latest iOS update might have changed something and I have found a way to get things sorted. When you do a search for emails where there are years of them, you now get an initial result that has a disclaimer at the bottom saying that “Some results may not appear. Mail downloads and organizes messages when iPad is locked, charging and connected to WiFi. Large accounts like this may take longer.” The search result pulls more old emails and they appear in different order as more are found, putting the newest lower in the result, as before, and you can’t find what you are looking for. BUT if you give it a bit of time and then change the search at the top from “From” to “To” and then back again to “From” the messages now appear in order from newest to oldest! The number of messages that you have from the sender is why people have said that different things work in the past - They must have been searching accounts that are smaller. I’ve tried this toggling now a few times and it has worked every time!