The problem depends on the fact that the other side sends the messages with an local coding different from yours.
This often happens to Fedora or Suse 9.1 users, who have a utf8 coding.
You can open the user-information for each contact which has this problem, and change the coding too iso8859-1, for example.
liquidat