自己レスですが、メール配信の件名だけが文字化けについては、admin/order/mail.phpの88行目
$objPage->tpl_subject = $objSendMail->subject;
を
$objPage->tpl_subject = mb_decode_mimeheader($objSendMail->subject );
とデコードすることで解決しました。
同様の件でお困りの方のご参考になれば幸いです。

ただし、送信されてくるメール件名そのものの文字化けは解決していません。

こちらは、ウェブメールでは正常表示しているのでEC-CUBEだけの問題ではないような気もするのですが・・・

なお、この掲示板でよく引用されているチェックでは下記の通り正常表示になっています。

string(8) "Japanese"
string(4) "美乳"
string(34) "=?ISO-2022-JP?B?GyRCSH5GfRsoQg==?="
string(34) "=?ISO-2022-JP?B?GyRCSH5GfRsoQg==?="
string(34) "=?ISO-2022-JP?B?GyRCSH5GfRsoQg==?="
string(34) "=?ISO-2022-JP?B?GyRCSH5GfRsoQg==?="
string(27) "mbstring.language: Japanese"
string(34) "mbstring.internal_encoding: EUC-JP"
string(27) "mbstring.http_input: EUC-JP"
string(28) "mbstring.http_output: EUC-JP"
string(32) "mbstring.encoding_translation: 1"

何かご指摘いただければ助かります。
宜しくお願いします。

再び自己レスです。

やはりXREA・CORESERVER特有の現象のようです。
下記を参考にして解決しました。

http://miniturbo.org/memo/2007/06/07/173627/#comment-570

件名の改行がらみの症状のようでしたので私の場合は、
data/class/GC_SendMail.phpの
$this->subject = mb_encode_mimeheader($subject);
を
$this->subject = mb_encode_mimeheader($subject,"ISO-2022-JP", "B", "\n");
とすることでクリアできました。

お騒がせしましたが、同様の症状でお困りの方はご参考になさってください。