I'm also suffering from this change to the Mail search app in iOS 7. All previous versions were just great -- you can knock down a complex search over a large inbox in a couple of quick iterations because you had control and knew what happened with each input.
Through a series of events I am in conversation with the internal Apple manager for the Mail app. I also happen to run my own email server with search engine and I can monitor the queries. So far I have gleaned a few bits of information.
1) Search results are grouped first, then listed in date order within each group. The groups in priority order are:
* Flagged
* From
* To/CC, Subject
* Body
2) When the match is on either the From or To field, a "pill" with that word shows up by the message summary to show that match.
3) When you type in a search phrase on your iDevice, it breaks the search down into one separate query per word and sends the query(ies) to the mail server asking for matches on any of the common fields (To, Cc, From, Subject) as well as in the body. In other words, if you type "bob jane party" it sends three separate search queries to the mail server asking for all messages that match "bob" in any field, "jane" in any field, and "party" in any field. The iDevice then organizes the search results from all three queries to conform with the order of result presentation above. (But note that the Bcc field is never requested to match.)
4) My own experiments show results that don't match the order in #1. There seems to be some kind of scoring being applied as well that is not (yet) described that seems to tweak results order beyond date order within a group.
5) The software manager also recommended using "attachment" as a search word if you are searching for an attachment, but like another poster above noted, it doesn't work. It's easy to see why: when the search query is sent to the email server, the word "attachment" is treated like any other search term; it doesn't match because, simply, it does not appear anywhere in the actual unformatted raw text of the message (which you can look at on a Mac or most other computers using Option-Command-U or similar on Thunderbird on PC).
I've given Apple feedback that the iOS 7 Mail search function is completely unusable. We (my wife, specifically, who is the power email searcher) has moved to AltaMail ($5) which is industrial strength -- lots of knobs and buttons and functionality, not very polished, but you have total control.
I highly recommend anyone with similar issues to voice their opinion at http://www.apple.com/feedback. Nobody at Apple reads this forum; complaining here does not go anywhere except other users.
Added info on "attachment" search word