E-mails going out in plain text

In an effort to look more professional our sales people are starting to use fancy signatures in their e-mails. Here’s the problem, the signatures work fine if they’re sending e-mail within the company, but once they send an e-mail to the outside world the e-mail is converted to plain text, thus losing the fancy signature. This has me scratching my head. We’re using Windows 2000 Server with Exchange 5.5. I’ve looked at every option I can find that talks about HTML, Rich, or plain text, and in every option I’ve removed the plain text option. As far as I can see the e-mails should not be getting converted. I’d really appreciate some help here.

Thanks,
-Brian Kline