[ntnn]

You should try AquaMail. The search works. Threads aren't shows as a tree, sadly, but they are grouped into a folder - not ideal but you can at least follow simple conversations. Still not something for mailing lists.

Additionally, AquaMail can handle nested folders, which K9 doesn't and never will, according to its developers.

[Arkanosis]

It's not free software, unfortunately, so that is a showstopper for me. Thanks for suggestion, though.

[PuffinBlue]

Does it allow plain text composing/viewing yet?

[Arkanosis]

Good question, this is also mandatory for me.