I seem to have better success if I make sure to ALWAYS click in the Search location popup that appears only after inputting some text (or numbers) into the search field. This is dumb/annoying UX because by default the search field is at the right side of the screen and the popup I am referring to is at the left side, in the sidebar, over your mailboxes and folders. Completely unintuitive. I almost always want to search All Mailboxes but am now worried that stuff won't work right unless I click there due to the problems I've been having. Anyway, it seems as though the workflow might have changed and I needed to alter how I do things. I thought I'd mention it here in case that was the same reason others were having problems.
NOTE: The "where to search" popup is not visible until you input something into the search field. Also, you can change where on the toolbar the Search field appears, but even at the leftmost position, it isn't adjacent to the "where to search" popup. Annoying!