SMTP clients can make a Message-ID themselves. They just have to be sure that the left-hand-side is sort of unique.
If the client doesn't make an ID the SMTP server will, but it will not tell the SMTP client what the ID is. One easy and safe way is to feed the message you're about to send (the entire message) through an MD5 or SHA1 hash, base64-encode the result and make an ID of the form <hash@doma.in> where hash is the base64'd hash and doma.in is the From field's domain.
The conventional way to connect replies is to use Message-ID and References. When you send a reply, you set your References to be concatenation of the original message's References and Message-ID fields.