Does it happen with specific people at the same email domain?
I had an issue with a user and it was their firewall, filtering system that was 'touching' the email messages somehow. They zapped an update on the box, and the problem went away. Strangest damn thing... I've heard Cisco ASA's can do demented things to SMTP traffic too, but that's probably not what's happening here.
Encoding is probably rare, but would cause issues. Do they get any of the message, or just jumbles. Reread your message, Hmm. Encoding, or a problem with their reader. What are they using? Plus, are other people from other email domains reporting issues reading your emails?