In addition to echoing what everyone else has to say about modules to use...

2. Is there any possibility where a "Message-ID" is not part of the mail header?

It's possible, but highly unlikely. Virtually every mail transport agent (sendmail, exchange, etc.) will add a message-id to a mail message if one isn't already there. Still, if this is production level code, you'd better test for the existence and complain if it's not found.

Mail header keywords are case-insensitive per the spec, and are separated from the message body by a single blank line.

Peace,
-McD