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...