Save the script as compiled script to /Library/Scripts/Mail Scripts, and update Mail's script menu. Use Sys Prefs to add in a keyboard shortcut for Mail to the script. The selected shortcut must be to one of the F-keys. The key selected to be the shortcut must be added to the script as property start_key. I have used the F1 key, as shown in the script. It is possible to use a key sequence other than a single F-key to start the script, but this makes the run handler more complicated, and I wanted it to be simple.
To use, order the message viewer either by sender, mailbox or subject; ascending or not doesn't matter. Then press the shortcut, and type the appropriate keys one-by-one. On slower machines, it will pay to wait until the message that most closely matches the previous key press is highlighted before proceeding with the next. The script will quit if no keys are pressed, after a user defined timeout. This is set at two seconds, with the property time_out line. This property can be adjusted for individual users.
Also note that the spaces cannot be used as a search key, as this tells Mail to scroll down one message, and interferes with the working of the script.
[robg adds: Due to the length of the script, I've uploaded it as a text file: mailkeys.txt. Just copy and paste the script into Script Editor, and this should work as described (with the required Jon's Commands, of course).]

