I solved this problem by no longer using my email as a task management tool. Emails that contain a new task get forwarded to Asana, where tasks are easier to deal with. This approach is closer to the Unix philosophy of narrowly scoped tools that can be effectively combined, and it's a philosophy that hasn't failed me yet.
"Gmail's conversation view is ... a tough natural language processing task"
Is it? How is it more than a different way of presenting threads?
Graphically, it shows all the messages in a continuous stream as opposed to only one message at a time. Since you now see all responses at once, there is no need for quoting any more, so quotes are collapsed.
I don't use Gmail any more, but conversation view is all but essential for me, too.
It doesn't seem to be. For most part, it's the same e-mail headers that every other e-mail client uses to show threads: http://www.jwz.org/doc/threading.html
Gmail's conversation view is in my opinion a nearly insurmountable barrier to entry for other companies. 1) It's a tough natural language processing task, which means startups have trouble with it. 2) It requires someone algorithmically reading all my emails, which means it's such a PR nightmare to even try it that only Google is willing to weather the storm.