I just noticed that Thunderbird has a really nice keyboard shortcut for "labelling" messages with one of six colors. From the message list, you can change the label of the selected message just by hitting a number from 0 to 5, 0 being normal (no special color). Suddenly, color labels have gone from "eh" to "wow!" in my personal productivity, especially with the number pad right next to the cursor keys.