Putting the generated ID into the subject (e.g. in square brackets preceding the actual text of the subject) is a fairly common method (e.g. Dell, Verizon, etc.).
If you're replying to an e-mail, then you don't change the subject - otherwise it's not replying, it's sending a new message. If the users don't recognize this and the fact that the subject was unique, well, then they deserve to have their replies lost. :p If you're genuinely concerned about it, though, you could put a small disclaimer at the top or bottom of the message instructing the users that the subject must not be altered when replying.
