Mail App search not finding recent emails in inbox Mac is running Sierra and using the mail app.

When I try to use the mail search function in the top right of the screen it doesnt find recent emails.  Ive tried changing the search context and looking in different mailboxes to no avail.  I've rebuilt the mailbox and also re-indexed the spotlight searc (because this is having the same issue but with files) to no avail.

Any ideas on what I could do to fix this?
I had the same issue when finding a 2015 email from my iCloud inbox. I switched to iCloud.com to find it. And I still have to go to the website even in High Sierra. Guess this has been a bug...