It seems like as long as the criteria for emails you're searching for are within your mail device setup, you don't have an issue.
But if the device is synching only 1 month, and I search for John Doe, and I have emails from John Doe that go beyond 1 month, it will index them as new, even though the device isn't set to be able to read them.
There's a disconnect between the data the device has access to via server search and the device options for mail.
This solved my problem. iPhone 6/128 running iOS 9 with and Exchange email address. It's sad that this is still an issue....