Yes, that's true. Every email has a unique ID and reply-to ID. It's surprising that Outlook and others are botching this.
I think threading is mostly done by some special headers, the "Re" is not that important (if at all, at least in Thunderbird). That is also the reason, why I don't recommend to start new threads by hitting reply and changing the subject. Such mails get buried in old threads and the chance that these won't get read are much higher.
