Tim:
Yet, when I do that with gmail (reply to a message through the web interface), it works with proper headers.
g:
that is interesting.
you have not done so regarding this "Subject:".
Because I have a bit more respect for the list than sending a mass of test emails through it when it's not needed. ;-) Brief summary:
I have logged into the gmail webpage, sent an email to an address. Replied to that email, outside of gmail. Replied to the reply, inside of gmail (using their web interface). And done more replies to replies. Results; proper headers in all the messages.
I have used Evolution with IMAP to gmail. Done the same sorts of tests (sending messages, replying to replies). Same results; proper headers.
That convinces me that gmail works properly, under normal circumstances. And I see that other people using gmail on this list have proper threading headers, too.
I'm not willing to bugger up my web browser with a pile of plug-ins to see if that makes it worse, though. And as brought up, it does look a bit like trolling (asking silly questions, in numerous places, doing it in an annoying fashion). On the other hand, the original question wasn't particularly laboured upon. So, I dunno.