Step 1 - Place foot in mouth
Well, after my rant on how OE doesn't support the full RFC850 spec, I did some more testing, debugging, whatever you want to call it, and determined that there was a hidden new line character appended to the end of the Message-ID which was causing the headaches. So, I guess OE was doing things right, it was just that darn extra character throwing things off. So, now would be the time to grab my foot and stick it firmly within my mouth!