What OS is this?

Since you lose the characters on the system that is creating the email, I would think that something (the program) is not seeing the different characters sets or the way the program was built it doesn't see use the character sets you need. Do you lose these characters in different programs or just mail (you might want to check this out as much as possible - it may not just be a single program problem)?

What version and type of mail? Are you using any special (Pine, ...) email client on the UNIX side? Any filters?