When I was on Brett Terpstra's Systematic podcast this week, we both bemoaned the inability to change search token criteria without using the mouse. Turns out we were both wrong. You can. The key shortcuts are:

Option-Command-F to get in the Apple Mail search bar (We got that one right).

Up Arrow, Down Arrow, Return to select a name.

Shift-Left Arrow to get into the search token selections, like To, From, Any.

Below is a 20 second screencast demonstrating it with 100% more banjo than anything I've ever made before. Thanks listener Thomas for the tip.

Here are the keyboard shortcuts to search Apple Mail. The tricking one is Shift+Left Arrow.