I quite like the iPhone's compromise: it stores and indexes the most recent 50 or so messages, and when searching provides a "Continue search on server" button.

I quite like the iPhone's compromise: it stores and indexes the most recent 50 or so messages, and when searching provides a "Continue search on server" button. Thunderbird (or others) could have a larger store of recent messages, but this would avoid downloading thousands of mailing list emails.