>上述のようなある程度の一意性を保てるなら、やは
>りMUA側でつけときたいのが人情 w

ならば Message-ID: <なんたらかんたら@default> というヘッダを生成する MSOE も
問題なしになるわけで。なんたらかんたらの部分はめったなことでは重複しないので。

メールアドレスの @ 以降は DNS でいうと MX レコードになるわけだが、
ホスト名だと A レコードになる。[email protected] さんが
Message-ID: <なんたらかんたら[email protected]> なら一意だろう、と
思っても、host.domain.name というホストにログインしている赤の他人の
hoge さんが <なんたらかんたら[email protected]> という Message-ID を
偶然生成してしまう可能性はゼロではない。しょせん完全な方法はない。

……という考え方もある。
（意訳:そういう狂信的な考えをする人もいるけど、わしが本心からそう思ってるわけではない）