自作のCGI(PHPのPEAR:Mailを使用)で、710と同じヘッダでInfoseek宛に
メール送信してみたが、文字化けはしない。

710の使っているCGIとHTMLのソースを見たら、原因が分かるかも。