Many apps have search features. Most are fairly self-explanatory to VoiceOver users. Search in the Mail app has some features that might be difficult to discover with VoiceOver and these are described here. The search feature in the Mail app can be extremely useful. So long as you can remember something about the message, who it was from, what it was about or just some text that is likely to appear somewhere in the mail, the search feature can help you find the message again. You can search just one of your mailboxes or all of them, including your deleted mail. Here's how it works.
Open the Mail app and return to your Inbox list if necessary. Explore near bottom centre of the scrreen to locate the "search field" and then double tap to begin editing it. Now, enter what you want to search for. This could be the name, or part of the name of the sender, a word or words from the subject or text that appears somewhere in the message. When you have finished entering the item to be searched for, touch near top centre of the screen to move VoiceOver's focus near the top of the list of search results and begin swiping right. You will hear something like "selected, all mailboxes, one of two" to indicate that you are currently searching all mailboxes. The next button, the second of two, is the "current mailbox" button. Double tap this only if you wish to restrict the search to the currently viewed mailbox. You will then hear the search results as you continue swiping right.
There is usually a top hits heading preceding messages that are thought to be the best matches. Swipe through these. Next there may be a suggestions heading. This will head a list of items matching the search text. There will be more, including items like Subject contains. You could double tap this to view a list of messages whose subject contains your search term.
Eventually you will reach the end of the search results and usually land back on the search field at the bottom of the screen.
I have taken you through the complete list of search results. Normally you would stop at the results that sounded most promising and double tap to discover what it revealed. This will either open a single message or reveal a list of messages. If necessary swipe through the list of messages and when you locate a promising message, double tap to open it. VoiceOver will normally be focused near the beginning of the text in the message body. If you want to know where the message was located, swipe left repeatedly if necessary and you will hear something like "folder, found in Gmail bin".
If you double tap on a person's name under the suggestions heading you will open a list of mails to or from that person. VoiceOver may be focused on the first message in the list. At present, the default choice is that this will be a list of messages from that person. If you want to search for either all messages sent to that person or both sent and received message, it is necessary to swipe left and select one of three buttons. These are "from", "to" and "message". If "message" is selected then the list includes all messages both to and from the person.
When you have finished with an individual message double tap on the back button at top left and you will return to the previous page of search results. Either look at other messages there or locate the Close button at bottom right and double tap to end the search.
When you originally enter the search text, there will be a search button at bottom right of the keyboard. If you double tap this, you will be presented with a list of messages that match the search term in any way. I'm not quite sure if this is a full list. I usually avoid double tapping the search button and swipe through the options to refine the search but that is just a personal preference. Some people will prefer the simplicity of using the search button on the keyboard as soon as the search text is entered.