mailの署名機能で文字化けしてしまう

mailにて、カラーテキストでHTML形式の英文の署名を作りました。署名といっても、上下にメッセージを入れる必要があったため、ひとつの署名の真ん中に本文を挿入するという形でメールを送りはじめたところ、windows利用の方々から、署名自体が変な添付ファイルとなりいくつも開いてしまう上に、日本語で書いた文章はすべて文字化けして読めないといわれました。（英文は大丈夫なようです。）
そこで、HTML形式（リッチテキスト）で署名を作る事をやめ、英文のプレーンテキストに変えたところ、署名自体のファイル化けはなくなりましたが、未だに日本語の文章を間に入れると文字化けしていて読めない、と言われる事があります。
OSやパソコンの機種を問わず確実に日本語のメールを署名と共に送る方法はないのでしょうか？