email header question

Does anybody know at what point an email message is assigned a "Message-ID:
<xxxx>" tag in its header?

I've got a program that's reading emails from a POP3 mailbox, and they don't
seem to have this tag present. However, it does show up later. I've heard
that you can store this tag in a local database to figure out which emails
have been read but not yet deleted so you don't show them again.

Thanks
-David Schwartz