Let's start things off with a key-shortcut gripe from Thunderbird 3. "Forward" is ⌘-L. Not ⌘-F (that's find-in-message, which is pretty common, if rarely used) or even ⌘-⇧-F, like it is in Mail. ⌘-⇧-F in Thunderbird brings up this bad boy:
We can talk more about search later, but for for the sake of the keyboard shortcut discussion, why not start with the nice search field in the toolbar? Google has taught us that a single text field is how we should do search, and we almost never need to fill out a big form to search for things.
Another thing the web has taught us is that ⌘-L is basically "go to the command line". It's so hardwired at this point that using that shortcut for anything other than a generalized command interface seems like a missed opportunity.