事前にS/MIMEでデジタル署名したメールを1回だけやりとりすれば大丈夫です。
このやりとりにより、相手側の証明書の公開鍵が自動的にメールソフトに取り込まれますので、次回からは暗号化が可能です。